线段树

线段树是一种维护区间信息的数据结构，用空间换时间，查询和修改基本都是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 }