Description

bLue 有一个神器的机器,这个机器可以读入一个数组,并按照用户要求快速地进行数组的处理和计算,它支持如下两种操作:

  • 操作 1:把数组中第 p 个元素的值增加 v。
  • 操作 2:计算数组中 [l, r] 区间内所有数的和。

这个机器就是这么的神奇,但是 bLue 的计算机坏掉了,你能帮他修一下吗?

Input

输入数据有多组(数据组数不超过 20),到 EOF 结束。

对于每组数据:

  • 第 1 行输入一个整数 n (1 <= n <= 10^5),表示数组中元素的个数。
  • 第 2 行输入 n 个用空格隔开的整数 ai (1 <= ai <= 10^10),表示初始输入到计算机中的数组。
  • 第 3 行输入一个整数 q (1 <= q <= 50000),表示用户的操作次数。
  • 接下来 q 行,每行输入先输入 1 个整数,表示操作类型,根据不同的操作类型:
    • 如果类型为 1,则紧接着输入 2 个用空格隔开的整数 p (1 <= p <= n) 和 v (1 <= v <= 10^10),表示要把数组中第 p 个数的值增加 v。
    • 如果类型为 2,则紧接着输入 2 个用空格隔开的整数 l, r (1 <= l <= r <= n),表示要计算区间 [l, r] 内所有数的和(数组下标从 1 开始)。

Output


对于每组数据中的每次类型为 2 的操作,输出 1 行,包含一个整数,表示计算出的和。


很明显的一道线段树的题,因为更新的是单个值,只需要利用线段树进行快速求和即可。所以用不到懒惰标记

代码:


#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxt = 100010;
ll aa[maxt];
ll ans[maxt<<2];
ll ls(ll p)
{
	return p<<1;
}
ll rs(ll p)
{
	return p<<1|1;
}
void push_up(ll p)
{
	ans[p] = ans[ls(p)]+ans[rs(p)];
}
void build(ll p,ll l,ll r)
{
	if(l==r)
	{
		ans[p] = aa[l];
		return ;
	}
	ll mid = (l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	push_up(p);
}
void updata(ll p,ll pos,ll l,ll r,ll k)
{
	if(l==r)
	{
		ans[p]+=k;
		return;
	}
	ll mid = (l+r)>>1;
	if(mid>=pos)
		updata(ls(p),pos,l,mid,k);
	else
		updata(rs(p),pos,mid+1,r,k);
	push_up(p);
} 
ll query(ll p,ll nl,ll nr,ll l,ll r)
{
	ll res = 0;
	if(l>=nl&&r<=nr)
	{
		return ans[p];
	}
	ll mid = (l+r)>>1;
	if(nl<=mid)
		res += query(ls(p),nl,nr,l,mid);
	if(nr>mid)
		res += query(rs(p),nl,nr,mid+1,r);
	return res;
}

int main()
{
	ll n;
	while(~scanf("%lld",&n))
	{
		ll lei,q,a,b,c,k;
		memset(ans,0,sizeof ans);
		memset(aa,0,sizeof aa);
		for(ll i=1;i<=n;i++)
			scanf("%lld",&aa[i]); 
		//cin>>aa[i];
		build(1,1,n);
		/*for(ll i=1;i<=n<<2;i++)
			cout<<ans[i]<<' ';*/
		//cin>>q;
		scanf("%lld",&q);
		for(ll i=1;i<=q;i++)
		{
		//	cin>>lei;
			scanf("%lld",&lei);
			if(lei==1)
			{
			//	cin>>a>>b; 
				scanf("%lld%lld",&a,&b);
				updata(1,a,1,n,b);
			}
			if(lei==2)
			{
			//	cin>>a>>b;
				scanf("%lld%lld",&a,&b);
				ll res = query(1,a,b,1,n);
				printf("%lld\n",res);
			}
		}
		
	}
}