给你N个数，有两种操作
1：给区间[a,b]的所有数都增加X
2：询问第i个数是什么？
第一行一个正整数n，接下来n行n个整数，再接下来一个正整数Q，表示操作的个数. 接下来Q行每行若干个整数。如果第一个数是1，后接3个正整数a,b,X，表示在区间[a,b]内每个数增加X,如果是2，后面跟1个整数i, 表示询问第i个位置的数是多少。
对于每个询问输出一行一个答案
3
1
2
3
2
1 2 3 2
2 3
5
数据范围
1<=n<=100000
1<=q<=100000
模板题
线段树就是二叉树加上一个迟缓标记，在进行区间修改的时候不直接修改整个区间的值，而是先对子树的根节点打上标记，标记可以累加，等到查询的时候再下放标记。
#include<bits/stdc++.h> using namespace std; const int MAXN=200005; struct treeN{ int val; int addM;//迟缓标记 }tree[MAXN*4]; int arr[MAXN]; void pushD(int root){//下移标记 if(tree[root].addM){ tree[root*2+1].addM+=tree[root].addM; tree[root*2+2].addM+=tree[root].addM; tree[root*2+1].val+=tree[root].addM; tree[root*2+2].val+=tree[root].addM; tree[root].addM=0; } } int sum(int a,int b){ return a+b; } void build(int root,int start,int end){ tree[root].addM=0; if(start==end) tree[root].val=arr[start]; else{ int mid=(start+end)/2; build(root*2+1,start,mid); build(root*2+2,mid+1,end); tree[root].val=sum(tree[root*2+1].val,tree[root*2+2].val); } } int query(int root,int start,int end,int qstart,int qend){ if(qstart>end||qend<start) return 0; if(qstart<=start&&qend>=end) return tree[root].val; pushD(root); int mid=(start+end)/2; return sum(query(root*2+1,start,mid,qstart,qend),query(root*2+2,mid+1,end,qstart,qend)); } void update(int root,int start,int end,int index,int val){ if(start==end){ if(start==index) tree[root].val+=val; return ; } int mid=(start+end)/2; if(index<=mid) update(root*2+1,start,mid,index,val); else update(root*2+2,mid+1,end,index,val); tree[root].val=sum(tree[root*2+1].val,tree[root*2+2].val); } void updateD(int root,int start,int end,int qstart,int qend,int val){ if(qstart>end||qend<start) return ; if(qstart<=start&&qend>=end){ tree[root].addM+=val; tree[root].val+=val; return ; } pushD(root); int mid=(start+end)/2; updateD(root*2+1,start,mid,qstart,qend,val); updateD(root*2+2,mid+1,end,qstart,qend,val); tree[root].val=sum(tree[root*2+1].val,tree[root*2+2].val); } int main(){ int n,i,j,x,y,m; cin>>n; for(i=0;i<n;i++) scanf("%d",&arr[i]); build(0,0,n-1); cin>>m; for(i=0;i<m;i++){ scanf("%d",&j); if(j==1){ scanf("%d%d%d",&x,&y,&j); updateD(0,0,n-1,x-1,y-1,j); } else{ scanf("%d",&j); cout<<query(0,0,n-1,j-1,j-1)<<endl; } } }
原文：https://www.cnblogs.com/wengsy150943/p/10679762.html