算法：线段树
哦吼！终于来学线段树啦~~
拖了好久都没有敢学，主要是基础知识点不熟，代码能力太弱。但是现在已经是时候了。
来看：
线段树（Segment Tree）几乎是算法竞赛最常用的数据结构了，它主要用于维护 区间信息 （要求满足结合律）。与树状数组相比，它可以实现 \(O(log\ n)\) 的 区间修改，还可以同时支持多种操作（加、乘），更具通用性。
线段树入门 - 敌兵布阵
题目描述
第一行有两个正整数 \(N\) 和 \(M\)，分别表示敌人有 \(N\) 个工兵营地，有 \(M\) 条命令。
第二行有 \(N\) 个正整数，第 \(i\) 个正整数 \(a_i\) 代表第 i 个工兵营地里开始时有 \(a_i\) 个人。
接下来有 \(M\) 行，每行有一条命令，命令有 \(3\) 种形式：
(1) \(Add \ i \ j\)，其中 \(i\) 和 \(j\) 为正整数，表示第 \(i\) 个营地增加 \(j\) 个人；
(2) \(Sub \ i \ j\)，其中 \(i\) 和 \(j\) 为正整数，表示第 \(i\) 个营地减少 \(j\) 个人；
(3) \(Query\ i\ j\)，其中 \(i\) 和 \(j\) 为正整数，表示询问第 \(i\) 到第 \(j\) 个营地的总人数；
线段树的建立
引用自[这篇文章][(https://zhuanlan.zhihu.com/p/106118909)]，写的挺好。
线段树是一棵 平衡二叉树。母结点代表整个区间的和，越往下区间越小。注意，线段树的每个 节点 都对应一条 线段（区间），但并不保证所有的线段（区间）都是线段树的节点，这两者应当区分开。
如果有一个数组[1,2,3,4,5]，那么它对应的线段树大概长这个样子：
每个节点 p 的左右子节点的编号分别为 \(2p\) 和 \(2p+1\)，假如节点 p 储存区间 [a,b] 的和，设 \(mid=(l+r)/2\)，那么两个子节点分别储存 [l, mid] 和 [mid+1,r] 的和。可以发现，左节点对应的区间长度，与右节点相同或者比之恰好多1。
线段树的变换只能说是无穷无尽，根据题目的需求具体写法可能也不同，所以这只能在实战中联系了。
AC 代码：（打错一点就要调好久）
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int sum[N<<2],a[N];
void build(int l,int r,int rt){
if(l==r){
sum[rt]=a[l];
return ;
}
int mid=(l+r)>>1;
build(l,mid,rt*2);
build(mid+1,r,rt*2+1);
sum[rt]=sum[rt*2]+sum[rt*2+1];
}
void update(int p,int add,int l,int r,int rt){
if(l==r){
sum[rt]+=add;
return;
}
int mid=(l+r)/2;
if(p<=mid) update(p,add,l,mid,rt*2);
else update(p,add,mid+1,r,rt*2+1);
sum[rt]=sum[rt*2]+sum[rt*2+1];
}
int query(int cl,int cr,int l,int r,int rt){
if(cl<=l&&r<=cr) return sum[rt];
int mid=(l+r)/2;
int ret=0;
if(cl<=mid) ret+=query(cl,cr,l,mid,rt*2);
if(cr>mid) ret+=query(cl,cr,mid+1,r,rt*2+1);
return ret;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
build(1,n,1);
while(m--){
char ch[10];
scanf("%s",ch+1);
int i,j;
scanf("%d%d",&i,&j);
if(ch[1]=='Q') printf("%d\n",query(i,j,1,n,1));
else if(ch[1]=='S') update(i,-j,1,n,1);
else if(ch[1]=='A') update(i,j,1,n,1);
}
return 0;
}