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); } } } }