线段树是一种二叉搜索数，一般用来实现动态的区间询问，与树状数组有相似之处，但是能用树状数组实现的操作都能用线段树实现。
一般线段树用于以下几种操作：
建树，单点修改，区间查询，区间修改。
首先要进行的就是建树：
void bui(int id,int l,int r) { if(l==r) { tr[id]=a[l]; return ; } int mid=(l+r)/2; bui(id*2,l,mid); bui(id*2+1,mid+1,r); tr[id]=max(tr[id*2],tr[id*2+1]);//tr[id]=tr[id*2]+tr[id*2+1]; }//查询最大值与区间和，最小值同理
单点修改：
void gexi(int id,int l,int r,int x,int v) { if(l==r) { tr[id]=v; return ; } int mid=(l+r)/2; if(x<=mid) gexi(id*2,l,mid,x,v); else gexi(id*2+1,mid+1,r,x,v); tr[id]=max(tr[id*2],tr[id*2+1]);//tr[id]=tr[id*2]+tr[id*2+1] }//查询最大值与区间和
区间查询：
int find(int id,int l,int r,int x,int y) { if(x<=l&&r<=y) { return tr[id]; } int mid=(l+r)/2,ans=0; if(x<=mid) ans=max(ans,find(id*2,l,mid,x,y));//ans+=find(id*2,l,mid,x,y); if(y>mid) ans=max(ans,find(id*2+1,mid+1,r,x,y));//ans+=find(id*2+1,mid+1,r,x,y); return ans; }
区间修改：
void push_up(int id) { tr[id]=tr[id*2]+tr[id*2+1]; } void push_down(int id,int l,int r) { if(lazy[id])//如果有lazy标记 { int mid=(l+r)/2; lazy[id*2]+=lazy[id];//左孩子的lazy加上它的lazy lazy[id*2+1]+=lazy[id];//右孩子的lazy加上它的lazy tr[id*2]+=lazy[id]*(mid-l+1); tr[id*2+1]+=lazy[id]*(r-mid); lazy[id]=0;//清除lazy标记 } } void qjgx(int id,int l,int r,int x,int y,int v) { if(x<=l&&r<=y)//[l,r]被[x,y]包含了 } { lazy[id]+=v;//暂时不下传修改的值，加进lazy标记 tr[id]+=v*(r-l+1); return ; } push_down(id,l,r);//要更新节点了，开始下传修改的值 int mid=(l+r)/2; if(x<=mid) qjgx(id*2,l,mid,x,y,v);//只有x<=mid(即[l,mid]有一部分是被[x,y]覆盖了的)才需要去更新[l,mid] if(y>mid) qjgx(id*2+1,mid+1,r,x,y,v); push_up(id); //子节点更新后父节点也更新 }
下面是两道例题，可以试着尝试一下这几种操作
一：敌兵布阵
敌人有 N 个工兵营地，编号 1∼N。
初始时，第 i 个营地有 ai 个人。
接下来有若干个命令，命令有 4 种形式：
Add i j，i 和 j 为正整数，表示第 i 个营地增加 j 个人。（j 不超过 30）
Sub i j，i 和 j 为正整数，表示第 i 个营地减少 j 个人。（j 不超过 30）
Query i j，i 和 j 为正整数（i≤j），表示询问第 i 到第 j 个营地的总人数。
End，表示结束，此命令只会作为最后一条命令出现。
请你计算每个 Query 的答案。
输入格式
第一行包含整数 T，表示共有 T 组测试数据。
每组数据第一行包含一个整数 N。
第二行包含 N 个整数 a1,a2,…,aN。
接下来若干行，每行包含一条命令，格式如题目所述。
输出格式
对于第 i 组数据，首先输出一行 Case i:，然后对于每个 Query 询问，输出一行一个整数，表示询问的段中的总人数。
数据范围
1≤T≤10,
1≤N≤50000,
1≤ai≤50,
每组数据最多有 40000 条命令，
保证任何营地的人数都不会减少为负数。
输入样例：
1. 1 2. 10 3. 1 2 3 4 5 6 7 8 9 10 4. Query 1 3 5. Add 3 6 6. Query 2 7 7. Sub 10 2 8. Add 6 3 9. Query 3 10 10. End
输出样例：
1. Case 1: 2. 6 3. 33 4. 59
AC代码：
#include <bits/stdc++.h> using namespace std; #define p 50010 int tr[4*p],a[4*p]; void bui(int id,int l,int r) { if(l==r) { tr[id]=a[l]; return ; } int mid=(l+r)/2; bui(id*2,l,mid); bui(id*2+1,mid+1,r); tr[id]=tr[id*2]+tr[id*2+1]; } int find(int id,int l,int r,int x,int y) { if(x<=l&&r<=y) { return tr[id]; } int mid=(l+r)/2,ans=0; if(x<=mid) ans+=find(id*2,l,mid,x,y); if(y>mid) ans+=find(id*2+1,mid+1,r,x,y); return ans; } void gexi(int id,int l,int r,int x,int v) { if(l==r) { tr[id]+=v; return ; } int mid=(l+r)/2; if(x<=mid) gexi(id*2,l,mid,x,v); else gexi(id*2+1,mid+1,r,x,v); tr[id]=tr[id*2]+tr[id*2+1]; } int main() { int t; scanf("%d",&t); for(int k=1;k<=t;k++) { int n; scanf("%d",&n); memset(a,0,sizeof(a)); memset(tr,0,sizeof(tr)); for(int i=1;i<=n;i++) scanf("%d",&a[i]); bui(1,1,n); char x[10]; int aa,bb,cc; cout<<"Case "<<k<<":"<<endl; while(~scanf("%s",x)) { if(x[0]=='Q') { scanf("%d%d",&aa,&bb); printf("%d\n",find(1,1,n,aa,bb)); } else if(x[0]=='A') { scanf("%d%d",&aa,&bb); gexi(1,1,n,aa,bb); } else if(x[0]=='S') { scanf("%d%d",&aa,&bb); gexi(1,1,n,aa,-bb); } else break; } } return 0; }
给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r，表示询问数列中第 l∼r 个数的和。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数 N,M。
第二行 N 个整数 A[i]。
接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
1≤N,M≤105,
|d|≤10000,
|A[i]|≤109
输入样例：
1. 10 5 2. 1 2 3 4 5 6 7 8 9 10 3. Q 4 4 4. Q 1 10 5. Q 2 4 6. C 3 6 3 7. Q 2 4
输出样例：
1. 4 2. 55 3. 9 4. 15
AC代码：
#include <bits/stdc++.h> #define int long long using namespace std; int sumv[10000001],n,m,a[10000001],lazy[10000001]; void push_up(int id) { sumv[id] = sumv[id * 2] + sumv[id * 2 + 1]; } void push_down(int id,int l,int r) { if(lazy[id]) { int mid = (l + r) / 2; lazy[id * 2] += lazy[id]; lazy[id * 2 + 1] += lazy[id]; sumv[id * 2] += lazy[id] * (mid - l + 1); sumv[id * 2 + 1] += lazy[id] * (r - mid); lazy[id] = 0; } } void bui(int id,int l,int r) { if(l == r) { sumv[id] = a[l]; return ; } int mid = (l + r) / 2; bui(id * 2,l,mid); bui(id * 2 + 1,mid + 1,r); sumv[id] = sumv[id * 2] + sumv[id * 2 + 1]; } void qjgx(int id,int l,int r,int x,int y,int v) { if(l >= x && r <= y) { lazy[id] += v; sumv[id] += v * (r - l + 1); return ; } push_down(id,l,r); int mid = (l + r) / 2; if(x <= mid) qjgx(id * 2,l,mid,x,y,v); if(y > mid) qjgx(id * 2 + 1,mid + 1,r,x,y,v); push_up(id); } int find(int id,int l,int r,int x,int y) { if(x <= l && r <= y) return sumv[id]; push_down(id,l,r); int mid = (l + r) / 2,ans = 0; if(x <= mid) ans += find(id * 2,l,mid,x,y); if(y > mid) ans += find(id * 2 + 1,mid + 1,r,x,y); return ans; } signed main() { cin>>n>>m; for(int i = 1; i <= n; i++) cin>>a[i]; bui(1,1,n); while(m--) { string p; int k,x,y; cin>>p>>x>>y; if(p == "C") { cin>>k; qjgx(1,1,n,x,y,k); } else cout<<find(1,1,n,x,y)<<'\n'; } return 0; }
