Link to this code:
https://cses.fi/paste/66df778b19dd205bf647f/
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mkp make_pair
#define take_input freopen("input.txt","r",stdin);freopen("output.txt","w",stdout)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pb push_back
const ll mxN = 2e5;
ll a[mxN];
ll tree[4*mxN+1];
void buildMinTree(ll idx,ll s,ll e)
{
if(s>e)
return;
if(s==e)
{
tree[idx]=a[s];
return;
}
ll m=s+((e-s)>>1);
buildMinTree(2*idx,s,m);
buildMinTree(2*idx+1,m+1,e);
tree[idx]=min(tree[2*idx],tree[2*idx+1]);
}
void buildSumTree(ll idx,ll s,ll e)
{
if(s>e)
return;
if(s==e)
{
tree[idx]=a[s];
return;
}
ll m=s+((e-s)>>1);
buildSumTree(2*idx,s,m);
buildSumTree(2*idx+1,m+1,e);
tree[idx]=tree[2*idx]+tree[2*idx+1];
}
ll queryMinTree(ll qs,ll qe,ll s,ll e,ll idx)
{
if(s>e or s>qe or e<qs)
return INT_MAX;
else if(qs<=s and qe>=e)
{
return tree[idx];
}
else
{
ll m=s+((e-s)>>1);
return min(queryMinTree(qs,qe,s,m,2*idx),queryMinTree(qs,qe,m+1,e,2*idx+1));
}
}
ll querySumTree(ll qs,ll qe,ll s,ll e,ll idx)
{
if(s>e or s>qe or e<qs)
return 0;
else if(qs<=s and qe>=e)
{
return tree[idx];
}
else
{
ll m=s+((e-s)>>1);
return querySumTree(qs,qe,s,m,2*idx)+querySumTree(qs,qe,m+1,e,2*idx+1);
}
}
void pointUpdateSumTree(ll s,ll e,ll idx,ll i,ll val)
{
if(s>e)
return;
if(s==e)
{
tree[idx]=val;
return;
}
else if(i<s or i>e)
return;
else
{
ll m = s+((e-s)>>1);
if(i>=s and i<=m)
pointUpdateSumTree(s,m,2*idx,i,val);
else
pointUpdateSumTree(m+1,e,2*idx+1,i,val);
tree[idx]=tree[2*idx]+tree[2*idx+1];
}
}
void pointUpdateMinTree(ll s,ll e,ll idx,ll i,ll val)
{
if(s>e)
return;
if(s==e)
{
tree[idx]=val;
return;
}
else if(i<s or i>e)
return;
else
{
ll m = s+((e-s)>>1);
if(i>=s and i<=m)
pointUpdateMinTree(s,m,2*idx,i,val);
else
pointUpdateMinTree(m+1,e,2*idx+1,i,val);
tree[idx]=min(tree[2*idx],tree[2*idx+1]);
}
}
int main()
{
fast;
// take_input;
ll n,q;
cin>>n>>q;
for(ll i=0;i<n;i++)
cin>>a[i];
ll idx=1;
buildSumTree(idx,0,n-1);
while(q--)
{
ll c1,a1,b1;
cin>>c1>>a1>>b1;
--a1,--b1;
if(c1==1)
{
idx=1;
pointUpdateSumTree(0,n-1,idx,a1,++b1);
}
else
{
idx=1;
cout<<querySumTree(a1,b1,0,n-1,idx)<<endl;
}
}
return 0;
}