线段树是一种维护区间信息的数据结构，用空间换时间，查询和修改基本都是O(logn)的。

线段树很好理解，常见模型比较固定。如单点修改，区间查询，区间修改等。

 

1 //单点修改，区间查询  2  3 int a[maxn],sum[4*maxn]; 4 void build(int p,int l,int r) { 5     if(l==r) sum[p]=a[l]; 6     else { 7         int mid=l+(r-l)/2; 8         build(2*p,l,mid); 9         build(2*p+1,mid+1,r);10         sum[p]=sum[2*p]+sum[2*p+1];11     }12 }13 void modify(int p,int l,int r,int x,int y) {14     if(l==r) sum[p]+=y;15     else {16         int mid=l+(r-l)/2;17         if(x<=mid) modify(2*p,l,mid,x,y);18         else modify(2*p+1,mid+1,r,x,y);19         sum[p]=sum[2*p]+sum[2*p+1];20     }21 }22 int query(int p,int l,int r,int x,int y) {23     if(x<=l&&y>=r) return sum[p];24     int mid=l+(r-l)/2,ans=0;25     if(x<=mid) ans+=query(2*p,l,mid,x,y);26     if(y>mid) ans+=query(2*p+1,mid+1,r,x,y);27     return ans;28 }

 

1 //区间修改，区间查询  2  3 typedef long long ll; 4 ll a[maxn],sum[4*maxn],lazy[4*maxn]; 5 void build(int p,int l,int r) { 6     if(l==r) sum[p]=a[l]; 7     else { 8         int mid=l+(r-l)/2; 9         build(2*p,l,mid);10         build(2*p+1,mid+1,r);11         sum[p]=sum[2*p]+sum[2*p+1];12     }13 }14 void add(int p,int l,int r,ll d) {15     lazy[p]+=d;16     sum[p]+=d*(r-l+1);17 }18 void pushdown(int p,int l,int r) {19     int mid=l+(r-l)/2;20     add(2*p,l,mid,lazy[p]);21     add(2*p+1,mid+1,r,lazy[p]);22     lazy[p]=0;23 }24 void modify(int p,int l,int r,int x,int y,ll d) {25     if(x<=l&&y>=r) add(p,l,r,d);26     else {27         pushdown(p,l,r);28         int mid=l+(r-l)/2;29         if(x<=mid) modify(2*p,l,mid,x,y,d);30         if(y>mid) modify(2*p+1,mid+1,r,x,y,d);31         sum[p]=sum[2*p]+sum[2*p+1];32     }33 }34 ll query(int p,int l,int r,int x,int y) {35     if(x<=l&&y>=r) return sum[p];36     pushdown(p,l,r);37     int mid=l+(r-l)/2;38     ll ans=0;39     if(x<=mid) ans+=query(2*p,l,mid,x,y);40     if(y>mid) ans+=query(2*p+1,mid+1,r,x,y);41     return ans;42 }