range sum query II

#include <bits/stdc++.h>
#define MOD                   (int)(1e9+7)
#define all(x)                x.begin(),x.end()
#define r_all(x)              x.rbegin(),x.rend()
#define lb                    lower_bound
#define ub                    upper_bound
#define pb                    push_back
#define IOfast                ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;

int64_t fenwick[(int)1e6];
int n,q;

//updating data in (logn)
void update(int node,int64_t val)
{
  for(int i = node;i<=n;i+=i&-i)
    fenwick[i]+=val;
}

//getting data in (logn)
int64_t get_ans(int node)
{
  int64_t ans = 0;
  for(int i = node;i;i-=i&-i)
     ans+=fenwick[i];
  return ans;
}

void solve()
{
  cin>>n>>q;
  vector<int64_t> arr(n);
  for(auto &item:arr) cin>>item;

  //creating fenwick tree
  //since fenwick is 1 based indexing therefore we are passing i + 1
  for(int i = 0 ;i<n;i++)
     update(i+1,arr[i]);

  while(q--)
  {
    int choice;
    cin>>choice;
    if(choice == 1)
    {
      int k ,u ;
      cin>>k>>u;
      int64_t diff = u - arr[k - 1];
      arr[k-1] = u; // changing value at arr[k-1] because of updation
      update(k,diff);
    }
    else
    {
      int a,b;
      cin>>a>>b;
      //geting ans for indexes
      // are are just doing commutative_frequency[b] - commutative_frequency[a-1]
      cout<<get_ans(b) - get_ans(a-1)<<"\n";
    }
  }
}

int main()
{
  IOfast;
  solve();
  return 0;
}