Submission #73368304

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define int long long
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
struct node{int l,r,s;}tr[N<<2];int a[N];
void pushup(int p){tr[p].s=tr[lc(p)].s+tr[rc(p)].s;}
void bt(int p,int l,int r)
{
	tr[p]={l,r,0};
	if(l==r){tr[p].s=a[l];return;}
	int mid=(l+r)>>1;
	bt(lc(p),l,mid);bt(rc(p),mid+1,r);
	pushup(p);
}
void change(int p,int x,int k)
{
	if(tr[p].r<x||tr[p].l>x)return;
	if(tr[p].l==tr[p].r)
	{
		tr[p].s=k;
		return ;
	}
	change(lc(p),x,k);change(rc(p),x,k);
	pushup(p);
}
int query(int p,int l,int r)
{
	if(tr[p].l>r||tr[p].r<l)return 0;
	if(l<=tr[p].l&&tr[p].r<=r)return tr[p].s;
	return query(lc(p),l,r)+query(rc(p),l,r);
}
signed main()
{
	int n,q;cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	bt(1,1,n);
	while(q--)
	{
		int op;cin>>op;
		if(op==1)
		{
			int x,y;cin>>x>>y;
			cout<<query(1,x,y)<<'\n';
		}
		else
		{
			int x,k;cin>>x>>k;
			change(1,x,k);
		}
	}
	return 0;
}

Submission Info

Judge Result