这是一道模板题。
给定数列 a[1],a[2],…,a[n]a[1],a[2],…,a[n]，你需要依次进行 qq 个操作，操作有两类：
1 l r x：给定 l,r,xl,r,x，对于所有 i∈[l,r]i∈[l,r]，将 a[i]a[i] 加上 xx（换言之，将 a[l],a[l+1],…,a[r]a[l],a[l+1],…,a[r] 分别加上 xx）；2 i：给定 ii，求 a[i]a[i] 的值。
Input
第一行包含 22 个正整数 n,qn,q，表示数列长度和询问个数。保证 1≤n,q≤1061≤n,q≤106。
第二行 nn 个整数 a[1],a[2],…,a[n]a[1],a[2],…,a[n]，表示初始数列。保证 |a[i]|≤106|a[i]|≤106。
接下来 qq 行，每行一个操作，为以下两种之一：
1 l r x：对于所有 i∈[l,r]i∈[l,r]，将 a[i]a[i] 加上 xx；2 i：给定 ii，求 a[i]a[i] 的值。
保证 1≤l≤r≤n,1≤l≤r≤n, |x|≤106|x|≤106。
Output
对于每个 2 i 操作，输出一行，每行有一个整数，表示所求的结果。
样例输入
3 2
1 2 3
1 1 3 0
2 2
样例输出
2思路：树状数组：https://blog.csdn.net/queque_heiya/article/details/105894492
注意：与https://blog.csdn.net/queque_heiya/article/details/105894492不同之于需要求出差分数组，难度要大于HDU1556
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<cstdio>
#define LL long long
using namespace std;
const int maxa=1e6+10;
LL n,q;
LL c[maxa];//前缀和
LL lowbit(LL i){return (i&-i);
}
void add(LL x,LL y){//更新 while(x<=n){c[x]+=y;x+=lowbit(x);}
}
LL sum(LL x){LL ans=0;while(x>0){ans+=c[x];x-=lowbit(x);}return ans;
}
int main(){LL c,b=0;scanf("%lld",&n);scanf("%lld",&q);for(int i=1;i<=n;i++){scanf("%lld",&c);add(i,c-b);b=c;} LL op,e1,e2,e3;for(int i=0;i<q;i++){scanf("%lld",&op);if(op==1){scanf("%lld",&e1);scanf("%lld",&e2);scanf("%lld",&e3); if(e1>e2) swap(e1,e2);add(e1,e3);add(e2+1,-e3);}else{scanf("%lld",&e1);printf("%lld\n",sum(e1));}}return 0;
}