一.原理：
2.可以维护的内容： sum,max,min等
struct node{ int l,r;//左右端点 int sum,maxx,minn;//要维护的值 }
3.示意图（直接盗用学长课件里的图啦）
线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是[a,b]，那么(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]。（来自课件）
（其实这个的原理跟模拟堆差不多，那篇博客被我鸽了 ）
4.说明：
区间[l,r]一般分为[l,mid],[mid+1,r]; mid=floor(l+r>>1);//下取整
二.基本操作：
1.建树（递归）
2.单点修改：
3.区间查询：
（1）、如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
（2）、如果这个区间的左儿子和目标区间有交集，那么递归左儿子
（3）、如果这个区间的右儿子和目标区间有交集，那么递归右儿子
三.代码：
1.pushup：用子节点更新当前节点信息
void pushup(int u){ tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum; }
2.build: 在一段区间上初始化线段树
void build(int u,int l,int r){ if(l==r){ tr[u].l=l;tr[u].r=r;tr[u].sum=w[r]; } else{ tr[u].l=l;tr[u].r=r; int mid=l+r >> 1; build(u << 1,l,mid);build(u<<1|1,mid+1,r); pushup(u); } }
3.update：单点修改
void update(int u,int x,int v){ if(tr[u].l==tr[u].r) tr[u].sum+=v; else{ int mid=tr[u].l+tr[u].r >> 1; if(x<=mid) update(u<<1,x,v); else update(u<<1|1,x,v); pushup(u); } }
4.query：区间查询
int query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum; int mid=tr[u].l+tr[u].r >> 1; int sum=0; if(l<=mid) sum=query(u<<1,l,r); if(r>mid) sum+=query(u<<1|1,l,r); return sum; }
四.模板题
原题链接：传送门（更好的阅读体验）
（洛谷上也有几道模板题的 可以去做）
题目描述
给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b] 的连续和。
输入格式
第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。
第二行包含 n 个整数，表示完整数列。
接下来 m 行，每行包含三个整数 k,a,b （k=0，表示求子数列[a,b]的和；k=1，表示第 a 个数加 b）。
数列从 1 开始计数。
输出格式
输出若干行数字，表示 k=0 时，对应的子数列 [a,b] 的连续和。
数据范围
1≤n≤100000,
1≤m≤100000，
1≤a≤b≤n
输入样例：
10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8
输出样例：
11
30
35
线段树解法：
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; int n,m,w[maxn]; struct node{ int l,r,sum; }tr[4*maxn]; void pushup(int u){ tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum; } void build(int u,int l,int r){ if(l==r){ tr[u].l=l;tr[u].r=r;tr[u].sum=w[r]; } else{ tr[u].l=l;tr[u].r=r; int mid=l+r >> 1; build(u << 1,l,mid);build(u<<1|1,mid+1,r); pushup(u); } } int query(int u,int l,int r){ if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum; int mid=tr[u].l+tr[u].r >> 1; int sum=0; if(l<=mid) sum=query(u<<1,l,r); if(r>mid) sum+=query(u<<1|1,l,r); return sum; } void update(int u,int x,int v){ if(tr[u].l==tr[u].r) tr[u].sum+=v; else{ int mid=tr[u].l+tr[u].r >> 1; if(x<=mid) update(u<<1,x,v); else update(u<<1|1,x,v); pushup(u); } } int main(){ cin>>n>>m; for(int i=1;i<=n;i++) cin>>w[i]; build(1,1,n); int op,x,y; while(m--){ cin>>op>>x>>y; if(!op) printf("%d\n",query(1,x,y)); else update(1,x,y); } return 0; }
树状数组解法：
#include<bits/stdc++.h> using namespace std; const int N = 1e5+6; int tr[N]; int a[N]; int n,m; int lowbit (int x){ return x&(-x); } void add(int x,int y){ for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=y; } int sum(int x){ int res=0; for(int i=x;i>0;i-=lowbit(i)) res+=tr[i]; return res; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; add(i,a[i]); } while(m--){ int k,x,y; cin>>k>>x>>y; if(k==0) cout<<sum(y)-sum(x-1)<<endl; else add(x,y); } return 0; }
五：进阶-区间修改
为了实现这个，引入一个新的状态——懒标记。
作用：存储到这个节点的修改信息，暂时不把修改信息传到子节点。
实现思路：
递归到这个节点时，只更新这个节点的状态，并把当前的更改值累积到标记中。
下传操作
①当前节点的懒标记累积到子节点的懒标记中。
②修改子节点状态。在引例中，就是原状态+子节点区间点的个数*父节点传下来的懒标记。
③父节点懒标记清0。
比较好的几篇博客呀：
