一行N个方格，开始每个格子里都有一个整数。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N<100000，,提问和修改的总数m<10000条。
输入描述 Input Description
输入文件第一行为一个整数N，接下来是n行n个整数，表示格子中原来的整数。接下一个正整数m，再接下来有m行，表示m个询问，第一个整数表示询问代号，询问代号1表示增加，后面的两个数x和A表示给位置X上的数值增加A，询问代号2表示区间求和，后面两个整数表示a和b，表示要求[a,b]之间的区间和。
输出描述 Output Description
共m行，每个整数
样例输入 Sample Input
6
4
5
6
2
1
3
4
1 3 5
2 1 4
1 1 9
2 2 6
样例输出 Sample Output
22
22
数据范围及提示 Data Size & Hint
1≤N≤100000， m≤10000 。
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
给你N个数，有两种操作
1：给区间[a,b]的所有数都增加X
2：询问第i个数是什么？
输入描述 Input Description
第一行一个正整数n，接下来n行n个整数，再接下来一个正整数Q，表示操作的个数. 接下来Q行每行若干个整数。如果第一个数是1，后接3个正整数a,b,X，表示在区间[a,b]内每个数增加X,如果是2，后面跟1个整数i, 表示询问第i个位置的数是多少。
输出描述 Output Description
对于每个询问输出一行一个答案
样例输入 Sample Input
3
1
2
3
2
1 2 3 2
2 3
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
数据范围
1<=n<=100000
1<=q<=100000
代码实现：
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 int n,m,a,b,c,d; 5 struct nate{int l,r,s;}t[600000];//线段树结构体。 6 void make_tree(int k,int l,int r){//建树。 7 int lson=k*2,rson=k*2+1;//定义左右儿子。 8 t[k].l=l;t[k].r=r;//填充k掌控区间的左右界限。 9 if(l==r){//如果到了叶节点，输入基值。 10 scanf("%d",&t[k].s); 11 return; 12 } 13 int mid=(l+r)/2;//注意mid是中间值偏左。 14 make_tree(lson,l,mid);//建造左子树。 15 make_tree(rson,mid+1,r);//建造右子树。 16 t[k].s=t[lson].s+t[rson].s;//求得k掌控区间的需求值（可以是和值，最小值，最大值等）。 17 } 18 void point_change(int k,int p,int v){//单点修改。 19 int lson=k*2,rson=k*2+1; 20 int l=t[k].l,r=t[k].r; 21 if(l==r){//对目标节点进行修改。 22 t[k].s+=v; 23 return; 24 } 25 int mid=(l+r)/2; 26 if(p<=mid) point_change(lson,p,v);//p在mid左侧，搜索左子树。 27 else point_change(rson,p,v);//p在mid右侧，搜索右子树。 28 t[k].s=t[lson].s+t[rson].s;//更改相关的节点的需求值。 29 } 30 void interval_change(int k,int l,int r,int v){//区间修改。 31 int lson=k*2,rson=k*2+1; 32 if(t[k].l==t[k].r){ 33 t[k].s+=v; 34 return; 35 } 36 int mid=(t[k].l+t[k].r)/2; 37 if(l<=mid) interval_change(lson,l,min(r,mid),v);//目前修改区间的左界在中间值左侧，说明左子树上有需要更改的节点，搜索左子树包含区间与目前修改区间的交集。 38 if(r>mid) interval_change(rson,max(l,mid+1),r,v);//目前修改区间的右界在中间值右侧，说明右子树上有需要更改的节点，搜索右子树包含区间与目前修改区间的交集。 39 t[k].s=t[lson].s+t[rson].s;//更改相关节点的需求值。 40 } 41 int point_query(int k,int p){//单点查询。 42 int lson=k*2,rson=k*2+1; 43 int l=t[k].l,r=t[k].r; 44 if(l==r) return t[k].s; 45 int mid=(l+r)/2; 46 if(p<=mid) return point_query(lson,p); 47 else return point_query(rson,p); 48 } 49 int interval_query(int k,int l,int r){//区间查询。 50 int lson=k*2,rson=k*2+1; 51 if(t[k].l==l&&t[k].r==r) return t[k].s; 52 int mid=(t[k].l+t[k].r)/2,ans=0; 53 if(l<=mid) ans+=interval_query(lson,l,min(r,mid));//目前查询区间的左界在中间值左侧，说明左子树仍有用，查询左子树包含区间与目前查询区间的交集。 54 if(r>mid) ans+=interval_query(rson,max(l,mid+1),r);//目前查询区间的右界在中间值右侧，说明右子树仍有用，查询右子树包含区间与目前查询区间的交集。 55 return ans; 56 } 57 int main(){ 58 scanf("%d",&n); 59 make_tree(1,1,n); 60 scanf("%d",&m); 61 for(int i=1;i<=m;i++){ 62 scanf("%d%d%d",&a,&b,&c); 63 if(a==1){ 64 65 } 66 if(a==2){ 67 68 } 69 } 70 return 0; 71 }
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 int n,m,a,b,c,d; 5 struct nate{int l,r,s;}t[600000]; 6 void make_tree(int k,int l,int r){ 7 int lson=k*2,rson=k*2+1; 8 t[k].l=l;t[k].r=r; 9 if(l==r){ 10 scanf("%d",&t[k].s); 11 return; 12 } 13 int mid=(l+r)/2; 14 make_tree(lson,l,mid); 15 make_tree(rson,mid+1,r); 16 t[k].s=t[lson].s+t[rson].s; 17 } 18 void point_change(int k,int p,int v){ 19 int lson=k*2,rson=k*2+1; 20 int l=t[k].l,r=t[k].r; 21 if(l==r){ 22 t[k].s+=v; 23 return; 24 } 25 int mid=(l+r)/2; 26 if(p<=mid) point_change(lson,p,v); 27 else point_change(rson,p,v); 28 t[k].s=t[lson].s+t[rson].s; 29 } 30 void interval_change(int k,int l,int r,int v){ 31 int lson=k*2,rson=k*2+1; 32 if(t[k].l==t[k].r){ 33 t[k].s+=v; 34 return; 35 } 36 int mid=(t[k].l+t[k].r)/2; 37 if(l<=mid) interval_change(lson,l,min(r,mid),v); 38 if(r>mid) interval_change(rson,max(l,mid+1),r,v); 39 t[k].s=t[lson].s+t[rson].s; 40 } 41 int point_query(int k,int p){ 42 int lson=k*2,rson=k*2+1; 43 int l=t[k].l,r=t[k].r; 44 if(l==r) return t[k].s; 45 int mid=(l+r)/2; 46 if(p<=mid) return point_query(lson,p); 47 else return point_query(rson,p); 48 } 49 int interval_query(int k,int l,int r){ 50 int lson=k*2,rson=k*2+1; 51 if(t[k].l==l&&t[k].r==r) return t[k].s; 52 int mid=(t[k].l+t[k].r)/2,ans=0; 53 if(l<=mid) ans+=interval_query(lson,l,min(r,mid)); 54 if(r>mid) ans+=interval_query(rson,max(l,mid+1),r); 55 return ans; 56 } 57 int main(){ 58 scanf("%d",&n); 59 make_tree(1,1,n); 60 scanf("%d",&m); 61 for(int i=1;i<=m;i++){ 62 scanf("%d%d%d",&a,&b,&c); 63 if(a==1){ 64 65 } 66 if(a==2){ 67 68 } 69 } 70 return 0; 71 }
高级数据结构基础---线段树的基本实现。
题目来源：CODE[VS]