本文章为2020年寒训用资料，有部分删减
线段树
引入
问题引入：
- 问题一：给定一个长度为\(n\)的数列，可以进行\(m\)次询问，每次询问查询区间\([l,r]\)内所有数的和
- 如果数据范围很小（例如\(n\leq 1000,m\leq 100\)），可以直接枚举。复杂度\(O(n)\)
- 如果数据范围较大（例如\(n\leq 1e6,m\leq 1e3\)），可以用前缀和。复杂度\(O(n+m)\)
- 问题二：给定一个长度为\(n\)的数列，可以进行\(m\)次操作，操作分两种，一种是修改单点的数值，另一种是查询区间\([l,r]\)内所有数的和
- 如果数据范围很小，依然可以枚举。复杂度\(O(n)\)
- 但大数据范围的情况下会TLE
- 此时即使使用前缀和，在进行修改操作后需要维护前缀和，故复杂度与枚举一致。大数据范围的情况下依然会TLE
- 问题三：给定一个长度为\(n\)的数列，可以进行\(m\)次操作，操作分两种，一种是修改区间\([l,r]\)内每个数的数值，另一种是查询区间\([l,r]\)内所有数的和
- 数据范围小的话当然可以枚举……
- 如果数据范围很大呢？（例如\(n\leq 1e6,m\leq 1e3\)）
线段树是什么
线段树是一种二叉树，它的基本思想是在二叉树的节点上保存区间信息，并在树上进行区间。下图是区间\([1,7]\)对应的线段树
上面这张图所表示的意思是，以求区间和为例，对于区间\([1,7]\)，其区间和等于其左儿子\(([1,4])\)的区间和加上其右儿子\([5,7]\)的区间和；而区间\([1,4]\)的区间和又等于区间\([1,2]\)和区间\([3,4]\)的和。对于一个区间\([lef,rig]\)，其左右儿子分别为\([lef,\lfloor(lef+rig)/2\rfloor]\)，\([\lfloor(lef+rig)/2\rfloor+1,rig]\)。对于线段树上的各节点，我们采取从上到下、从左往右的编号方法。具体而言，以上图为例，\([1,7]\)是编号为1，\([1,4]\)编号为2，\([5,7]\)编号为3……
对于查询与修改，线段树的复杂度都是\(O(\log_2n)\)
建树
根据线段树的结构和节点编号方式，我们很容易得到以下建树方式
int sum[maxn<<2]
void pushup(int rt)
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int lef,int rig,int rt)
{
if(lef==rig){
int tmp;
scanf("%d",&tmp);
sum[rt]=tmp;
return ;
}
int mid=(lef+rig)/2;
build(lef,mid,rt<<1);
build(mid+1,rig,rt<<1|1);
pushup(rt);
}代码很短，但有些地方可能会让初次接触的人稍微有点疑惑：
maxn<<2是什么意思？
此处maxn表示的是最大区间长度，maxn<<2等同于4 * maxn。sum是用来存我们的线段树节点的数组。为什么需要开4倍大的空间呢？首先，线段树是一棵完全二叉树， 对于一棵完全二叉树，假如有\(n\)个叶子节点（对应到线段树上就是区间总长度为\(n\)），其总节点数为\(2n-1\)。似乎开2倍就够了呢……但经验告诉我们，开四倍是较为保险的选择，既不会太大导致MLE，也不会太小导致越界。
rt<<1和rt<<1|1
由于线段树节点的编号方式，父节点和其两个子节点的编号存在这样的关系：\[id_{leftson}=2\times id_{father}\]，\[id_{rigson}=2\times id_{father}+1\]
为了提高速度，我们使用位运算来代替乘法、加法。
pushup
父亲节点的信息来自于两个子节点，故在完成子节点的建立后，我们要用两个子节点来建立父亲节点
单点操作
单点操作包括单点查询与单点修改
单点查询
单点查询的大致思想与二分查找类似。如果需要查询的位置\(pos\)在当前区间的左侧，则查找当前区间的左儿子；否则，查找当前区间的右儿子。重复这一过程，直至区间左右端点相等，则说明已经找到。
代码如下：
int ans;
void query(int pos,int lef,int rig,int rt)
{
if(lef==rig){
ans=sum[rt];
return ;
}
int mid=(lef+rig)/2;
if(pos<=mid) query(pos,lef,mid,rt<<1);
else if(pos>mid) query(pos,mid+1,rig,rt<<1|1);
}单点修改
单点修改代码如下：
void update(int pos,int val,int lef,int rig,int rt)
{
if(lef==rig){
sum[rt]+=val;
return ;
}
int mid=(lef+rig)/2;
if(pos<=mid) update(pos,val,lef,mid,rt<<1);
else if(pos>mid) update(pos,val,mid+1,rig,rt<<1|1);
pushup(rt);
}与单点查询基本一致，但要记得最后pushup一下来更新父节点。
区间操作
区间操作的总体思想是，对于带查询的区间\([L,R]\)，如果当前区间\([lef,rig]\)完全包含在带查询区间中，就直接将\([lef,rig]\)上的信息统计到答案中。如下所示 \[ \underbrace{L,L+1,\dots \overbrace{lef,lef+1,\dots ,rig-1,rig}\dots ,R-1,R} \] 否则，如果当前区间不是完全包含在待查询区间内，就查询左儿子或右儿子。如下所示 \[ \rlap{\overbrace{\phantom{lef,lef+1,\dots,L,L+1,\dots,rig-1,rig}}} lef,lef+1,\dots, \underbrace{L, L+1,\dots,rig-1,rig,\dots,R-1,R} \]
区间查询
借用上面所提到的总体思想，可以写出这样的代码：
int query(int L,int R,int lef,int rig,int rt)
{
if(lef>=L&&rig<=R){
return sum[rt];
}
int mid=(lef+rig)/2;
int ret=0;
if(L<=mid) ret+=query(L,R,lef,mid,rt<<1);
if(R>mid) ret+=query(L,R,mid+1,rt<<1);
}区间修改
借用单点修改的思想，很容易想到，区间修改就是相当于调用多次单点修改，把区间内的数字都修改了。举个例子，对于区间\([1,7]\)，如果我们要修改\([2,7]\)内的数，那最终被修改的节点如下图所示 
一个很明显的问题在于，这样做的话，复杂度会比直接暴力修改还高！而且，如果我要查询的只是\([5,7]\)的子区间，那就会存在不必要的修改。比如说我要查询\([1,5]\)，那\([5,6]\)等等的修改就没有用。
事实上，要修改区间\([2,7]\)，我们可以仅仅修改我们需要的区间。具体而言，修改的时候只需要修改\([1,7],[1,4],[1,2],[2,2],[3,4],[5,7]\)。等到需要查询这些区间以外的区间时，再去进行相应的修改。这就是懒惰标记（lazy tag）的思想
所谓懒惰，就是“要用的时候才用，否则就不用”。具体来说，懒惰标记用于存储父节点的修改信息，但暂时不把信息传给子节点，等到需要用到子节点时再把信息传给子节点。
加上了懒惰标记的区间修改代码如下：
void pushdown(int rt,int len)
{
if(lazy[rt]){
lazy[rt<<1]+=lazy[rt];
lazy[rt<<1|1]+=lazy[rt];
sum[rt<<1]=lazy[rt<<1]*(len-(len>>1));
sum[rt<<1|1]=lazy[rt<<1|1]*(len>>1);
lazy[rt]=0;
}
}
void update(int L,int R,int val,int lef,int rig,int rt)
{
if(lef>=L&&rig<=R){
sum[rt]+=val*(rig-lef+1);
lazy[rt]+=val;
return ;
}
pushdown(rt);
int mid=(lef+rig)/2;
if(L<=mid) update(L,R,val,lef,mid,rt<<1);
if(R>mid) update(L,R,val,mid+1);
pushup(rt);
}加上懒惰标记后，同样是修改\([2,7]\)这一区间，被修改的区间如下所示：
另外，在引入了懒惰标记后，单点查询、区间查询的代码也要更改（其实就是加上pushdown而已）。具体如下：
单点查询：
int query(int pos,int lef,int rig,int rt)
{
if(lef==rig){
return sum[rt];
}
pushdown(rt);
int ret=0;
int mid=(lef+rig)/2;
if(lef<=mid) ret+=query(pos,lef,mid,rt<<1);
else if(rig>mid) ret+=query(pos,mid+1,rig,rt<<1|1);
return ret;
}区间查询：
int query(int L,int R,int lef,int rig,int rt)
{
if(L>=lef&&R<=rig){
return sum[rt];
}
pushdown(rt);
int ret=0;
int mid=(lef+rig)/2;
if(L<=mid) ret+=query(L,R,lef,mid,rt<<1);
if(R>mid) ret+=query(L,R,mid+1,rig,rt<<1|1);
return ret;
}减法运算和乘法运算
上面所提到的都是修改与查询都是基于加法的，那如果是减法、乘法、除法呢？
如果是减法的话就直接加上负数即可。
如果是乘法或除法的话，就要另当别论。
（此处只讨论区间查询与区间修改，如果区间的会了，单点肯定也会吧 :D）
对于乘法，只需要像这个样子修改update：
void update(int L,int R,int val,int lef,int rig,int rt) { if(lef>=L&&rig<=R){ lazy[rt]*=val; sum[rt]*=lazy[rt]; return ; } pushdown(rt); int mid=(lef+rig)/2; if(L<=mid) update(L,R,val,lson); if(R>mid) update(L,R,val,rson); }这样修改pushdown：
void pushdown(int rt) { if(lazy[rt]!=1){ lazy[rt<<1]*=lazy[rt]; lazy[rt<<1|1]*=lazy[rt]; sum[rt<<1]=sum[rt<<1]*lazy[rt]; sum[rt<<1|1]=sum[rt<<1|1]*lazy[rt]; lazy[rt]=1; } }另外要记得初始化lazy中所有数为1
PS：思考一下，如果是乘法和加法同时进行，即区间修改操作中，既可以将区间上的数乘以一个数，也可以将区间上的数加上一个数，那要怎么维护sum和lazy呢？
离散化
所谓离散化指的是，在某些情况下，由于数据范围过大，直接保存数据的做法会导致MLE；但要解出题目其实并不需要保存实际的数据，只需要保存数据之间的相对大小即可。举个例子，现在要在一条长度为\(1e9\)的线段上进行区间染色，颜色与颜色之间会相互覆盖，求最终线段上可以看到多少种颜色。显然，我们不可能开一个长度为\(4e9\)的数组来存线段树节点，也不可能开一个长度为\(4e9\)的数组来存懒惰标记。如何解决这一问题呢？注意到，我们现在其实并不关心被染色的线段具体有多长，而只关心线段之间的关系（相对大小，位置关系）。所以我们可以为每一个需要染色的区间的左右端点分配一个id，并通过id来建立线段树。所有的修改与查询都在这棵”id线段树“上进行。离散化的实际实现一般通过sort()和unique。
下面用一道例题来讲解：
题目大意是说，有一堵长为10000000，现在要在墙上贴\(n(1\leq n\leq 10000)\)张海报（海报与海报之间会相互覆盖），问贴完所有海报后，能看到的海报有多少张？
与上面提到的染色问题思路一致，将每张海报离散化后，用离散化得到的id建立线段树，并通过query查询能看到的海报的数目。完成离散化后，通过lower_bound()查询左右端点对应的id。
参考代码：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
const int maxn=10005;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int vis[10000+5];
int lazy[maxn<<3];
struct node{
int lef;
int rig;
};
node ps[20000+5];
void pushdown(int rt)
{
if(lazy[rt]!=0){
lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
lazy[rt]=0;
}
return ;
}
int ans=0;
void update(int toL,int toR,int todo,int lef,int rig,int rt)
{
if(toL<=lef&&toR>=rig){
lazy[rt]=todo;
return ;
}
pushdown(rt);
int mid=lef+(rig-lef)/2;
if(toL<=mid)
update(toL,toR,todo,lson);
if(toR>mid)
update(toL,toR,todo,rson);
return ;
}
void query(int lef,int rig,int rt)
{
if(lazy[rt]){
if(!vis[lazy[rt]]){
ans++;
vis[lazy[rt]]=1;
}
return ;
}
if(lef==rig)
return ;
pushdown(rt);
int mid=lef+(rig-lef)/2;
if(lef<=mid)
query(lson);
if(rig>mid)
query(rson);
}
int lsh[maxn<<2];
int main()
{
int t;
cin>>t;
while(t--){
int idx=0;
mst(lsh,0);
mst(lazy,0);mst(vis,0);
ans=0;
int n;cin>>n;
for(int i=0;i<n;i++){
scanf("%d %d",&ps[i].lef,&ps[i].rig);
lsh[idx++]=ps[i].lef;lsh[idx++]=ps[i].rig;
}
sort(lsh,lsh+idx);
int cnt=unique(lsh,lsh+idx)-lsh;
for(int i=0;i<n;i++){
int L=lower_bound(lsh,lsh+cnt,ps[i].lef)-lsh+1;
int R=lower_bound(lsh,lsh+cnt,ps[i].rig)-lsh+1;
update(L,R,i+1,1,cnt+1,1);
}
query(1,cnt+1,1);
printf("%d\n",ans);
}
return 0;
}拓展
拓展内容包括：
区间除、维护区间平方和、维护区间立方和、区间位运算...
- 扫描线
- 权值线段树
- 主席树
etc...
树状数组
引入
所谓树状数组，就是用数组来模拟树形结构，常用于解决一些区间问题（区间加、区间求和等）。相较于线段树，其优点在于常数更小，且代码更短。缺点在于功能比较有限，对于一些复杂的区间问题很难解决，甚至是无法解决。可以说，能用树状数组解决的问题都能用线段树解决，但能用线段树解决的问题不一定能用树状数组解决。
辅助数组c与lowbit
首先，定义一个序列\(a_n\)，其长度为\(n(1\leq n\leq1e6)\)，可进行\(m(1\leq m \leq 1e3)\)次操作，每次操作要么是对一个数加上一个数值（单点修改），要么是查询一段区间内的总和（区间查询）。
这一问题当然可以用上面所说的线段树来解决，但现在我们引入树状数组。
首先定义函数\(lowbit(x)\)，有 \[ lowbit(x)=x\&(-x) \]
\(lowbit(x)\)的具体含义在于，求出\[x\]最低位1所对应的值。比方说，\[lowbit(10100_2)=100_2=4_{10}\]，\[lowbit(10001111_2)=1_2=1_{10}\]，\[lowbit(100010_2)=10_2=2_{10}\]
再定义一个辅助数组\(c_i\)，有 \[$ c_i=a_{i}+a_{i-1}+\dots+a_{i-lowbit(i)+1} \]$
也就是说，c[i]表示的是, 从a[i]开始，一直到 a[i-lowbit(i)+1] 这一长度为lowbit(i) 的连续区间的总和。如下图
构建出来的树状数组大致长下面这个样子
修改与查询
此处只考虑单点修改和区间查询。
单点修改：当我们要修改\[a_j\]的时候，因为有\[c_i=a_i+a_{i-1}+\dots+a_{i-lowbit(i)+1}\]，所以修改一个数可能会导致多个\[c_i\]的改变。所以我们这么编写单点修改的代码：
对于区间查询，\(c_i\)的定义让我们想到，是否可以通过求前缀和的方法求区间和。因此，查询的代码可以这样编写：
通过观察修改、查询的代码，以及树状数组的结构，我们可以看出，树状数组其实巧用二进制来对整个序列进行分段。以一个长度为7的序列为例，有 \[ \begin{aligned} lowbit(1)&=1,c_1=a_1;\\ lowbit(2)&=2,c_2=a_2+a_1;\\ lowbit(3)&=1,c_2=a_3;\\ lowbit(4)&=4,c_4=a_4+a_3+a_2+a_1;\\ lowbit(5)&=1,c_5=a_5;\\ lowbit(6)&=2,c_6=a_6+a_5;\\ lowbit(7)&=1,c_7=a_7; \end{aligned} \] 我们把这些数据套到query()代码中，可以发现，加上的\(c[i]\)分别是\(c[7],c[6],c[4]\)，也就是\(a[7],a[6]+a[5],a[4]+a[3]+a[2]+a[1]\)这三段。