线段树（Segment Tree）是一种基于分治思想的数据结构，可以在 \(\mathcal{O}(\log~n)\) 的时间内完成区间修改和区间查询等操作。
1.1 线段树基础
此部分介绍普通线段树的基本思想与操作。
1.1.1 基本思想
线段树本质上就是一棵二叉树，它的每一个节点表示一段区间的信息，对于一个长度不为 \(1\) 的区间 \([l,r]\) ，它的左右儿子分别表示 \([l,\lfloor \frac{l+r}{2} \rfloor]\) 和 \([\lfloor \frac{l+r}{2} \rfloor+1,r]\) 的信息，这样我们就把整个序列划分成了一个树形结构。
当我们维护好线段树后，对于每一次询问，便可以利用已知的节点合并成我们想要的答案。例如我们想要知道区间 \([4,9]\) 的信息，我们只需要知道区间 \([4,6]\) 与区间 \([7,9]\) 的信息即可，极大地优化了时间复杂度。而对于修改，只需要修改影响到的节点即可，具体操作可见下文。
总结一下，线段树的基本思想实质上是一种基于二进制拆分，利用分治思想，归并得到答案的方法。
1.1.2 基本操作
为了方便起见，我们举一个具体的问题：
有一个长度为 \(n\) 的序列 \(a\) ，要求支持以下两种操作：
- 将某区间每一个数加上 \(k\)。
- 求出某区间每一个数的和。
其中 \(1 \le n \le {10}^5\) 。
建树
首先我们考虑如何确定点的编号，由线段树的定义可知，线段树实质就是一棵二叉树，所以我们考虑用二叉树的编号方式给线段树编号，具体方法如下：
- 对于一个编号为 \(x\) 的点，其左儿子的编号为 \(2 \times x\) ，其右儿子的编号为 \(2 \times x +1\) 。
接下来就是确定每个节点的左右区间边界，依据线段树的定义可知：
- 对于一个长度不为 \(1\) 的区间 \([l,r]\) ，它的左右儿子管辖的区间分别为 \([l,\lfloor \frac{l+r}{2} \rfloor]\) 和 \([\lfloor \frac{l+r}{2} \rfloor+1,r]\) 。
具体实现时，显然需要用到递归的方法，从编号为 \(1\) 管辖区间为 \([l,r]\) 的根节点开始，每次依据上述方法更新其左右儿子，如果当前节点区间长度为 \(1\) ，那么它就是叶子节点，他的区间和直接从序列 \(a\) 赋值即可，否则当左右儿子递归结束返回时，需要合并其两个子节点的信息，具体代码如下：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+10;
int n,q;
ll a[N];
struct Tree
{
int l,r,sz;
ll sum,lazy;
}T[N<<2];//需要维护的基本信息
void push_up(int x)//上浮操作
{
T[x].sum=T[x<<1].sum+T[x<<1|1].sum;
}
void init(int l,int r,int x)
{
T[x]={l,r,r-l+1,0,0};
if(l==r)
{
T[x].sum=a[l];
return;
}
int mid=l+r>>1;
init(l,mid,x<<1);
init(mid+1,r,x<<1|1);
push_up(x);//归并得到x的信息
return;
}
其中 push_up 操作的含义是将儿子的节点信息合并得到父节点的信息，它被称为上浮操作。
接下来，我们分析一下建树的时间复杂度与空间复杂度。关于空间复杂度，需要考虑建树的过程中一共开了多少个点，我们具体分析一下：
首先，为方便起见，称根节点为第 \(0\) 层。易可以看出线段树一共有 \(\lceil \log_2 n \rceil\) 层，又由于其是一棵完全二叉树，所以共有 \(\sum\limits_{i=0}^{\lceil \log_2 n \rceil} 2^i = 2^{\lceil \log_2 n \rceil+1}-1\) 个节点，其中 \(\lceil \log_2 n \rceil\) 最大能取到 \(\log_2 n+1\)，所以最多共有 \(2^{\log_2 n+2}-1=4 \times n-1\) 个节点，所以空间复杂度也是 \(\mathcal{O}(n)\) 级别的，但是线段树开空间的时候需要开 \(4\) 倍空间。
关于时间复杂度，由于一共遍历了 \(4 \times n-1\) 个节点，所以时间复杂度显然是 \(\mathcal{O}(n)\) 的。
区间查询
建好线段树后，我们便可以在线段树上进行区间查询。由于二进制的性质，对于区间 \([l,r]\) ，我们可以将其拆分成最多 \(\log n\) 个区间，只要在线段树上找到这些区间，并将他们归并起来，我们便可以得到答案了。
区间查询我们同样使用递归算法，实现如下：
ll query(int l,int r,int x)//我们要查询区间[l,r]，现在到达的节点编号为x
{
ll ans=0;
if(l<=T[x].l&&T[x].r<=r)//如果说这个区间被需要查询的区间完全包含，那么就直接返回
{
return T[x].sum;
}
int mid=T[x].l+T[x].r>>1;
if(l<=mid) ans+=query(l,r,x<<1);//如果左区间与需查询区间有交集，递归左区间。
if(r>mid) ans+=query(l,r,x<<1|1);//右区间同理
return ans;
}
区间查询的复杂度是 \(\mathcal{O}(\log n)\) 的，具体证明如下：
由于查询区间是连续的，所以在每一层中，只有最左边和最右边的节点所代表的区间才有可能没有被完全覆盖，那么传到下一层的时候，最多只有 \(4\) 个节点。同理，查询时每一层最多也只能访问 \(4\) 个节点。由于树共有 \(\lceil \log_2 n \rceil\) 层，复杂度显然是 \(\mathcal{O}(\log n)\) 的，命题得证。
区间修改与懒惰标记的应用
对于区间修改，最直接的方法就是将被修改区间 \([l,r]\) 完全覆盖的所有节点都修改一遍，但这种方法的复杂度我们显然无法承受。于是我们引入一种方法，称为懒惰标记。
对于一个被修改区间完全覆盖的节点，显然它的所有子孙节点也被完全覆盖。此时我们考虑不修改它的子孙节点的信息，而是在此节点打一个标记，等到需要用到它的子孙节点的信息时在依据此节点的标记修改它们，这样可以大大减少时间复杂度。由于这是一种通过延迟对节点信息的更改的方法，故被称为懒惰标记。
加入了懒惰标记之后，易发现它的复杂度与区间查询的复杂度是一样的，故为 \(\mathcal{O}(\log n)\) 。
知道了它的思想，我们便可以具体实现出来：
void f(ll num,int x)
{
T[x].sum+=num*T[x].sz;
T[x].lazy+=num;
}//将具体如何修改写成函数，更加便利
void push_down(int x)
{
if(T[x].lazy==0)
{
return;
}
f(T[x].lazy,x<<1);
f(T[x].lazy,x<<1|1);
T[x].lazy=0;
}//下沉操作
void modify(int l,int r,int x,ll num)
{
if(l<=T[x].l&&T[x].r<=r)
{
f(num,x);//如果完全包含，打上标记，仅修改此节点的信息
return;//直接返回，不修改子孙节点
}
push_down(x);//需要用到x儿子的信息，取消标记，下放信息
int mid=T[x].l+T[x].r>>1;
if(l<=mid) modify(l,r,x<<1,num);
if(r>mid) modify(l,r,x<<1|1,num);
push_up(x);//上浮操作，归并得到x节点的信息。
return;
}
其中 push_down 操作被称为下沉操作，具体含义是取消当前节点的标记，将修改下放到左右儿子。
引入了懒惰标记之后，我们发现区间查询操作也需要修改一下，具体见下文：
ll query(int l,int r,int x)
{
ll ans=0;
if(l<=T[x].l&&T[x].r<=r)
{
return T[x].sum;
}
push_down(x);//我们下文需要用到x子节点的信息，但有可能还未更改，故进行一步下沉操作。
int mid=T[x].l+T[x].r>>1;
if(l<=mid) ans+=query(l,r,x<<1);
if(r>mid) ans+=query(l,r,x<<1|1);
return ans;
}