线段树简介
线段树是一种基于分治思想的二叉树结构，用于区间信息统计
线段树对比树状数组有如下好处：
- 每个节点都代表一个区间
- 具有唯一根节点，代表 $[1,N]$
- 每个叶子节点代表一个元素
- 可以用二叉树的方式存储（详见下面）
$$\scriptsize\textcolor{grey}{区间视角}$$
$$\scriptsize\textcolor{grey}{树视角}$$
因为线段树接近完全二叉树，故可以用如下表示方法：
- 根节点编号为 $1$
- 编号为 $X$ 的节点左子节点编号为 $2X$
- 编号为 $X$ 的节点右子节点编号为 $2X+1$
线段树特性:
- 长度是 $n$ 的序列构造线段树，这颗线段树有 $2n-1$ 个节点（同二叉树叶子节点与所有节点数量的关系），高度为 $logn$。
- 存线段树的数组要开 $\mathbf{4}$ 倍空间！
线段树实现
1.建树
先定义一个线段树的结构体：
struct tree{
int l,r;//区间信息
int sum,tag;//区间和及标记
//其他变量的定义参考题目
}t[40010];
再从上到下构建线段树，并从下往上传值，可用递归实现
void build(int x,int l,int r){
t[x].l=l,t[x].r=r;//传递区间[l,r]
if(l==r){
t[x].sum=a[l];
return;
}//此点如是叶子节点则结束递归
int mid=(l+r)>>1;//区间中点
build(x*2,l,mid);//构造左子树
build(x*2+1,mid+1,r);//构造右子树
t[x].sum=t[x*2].sum+t[x*2+1].sum;//从下往上传值
}
调用入口：build(1,1,n);
2.基础修改与查询
1.单点修改与查询
线段树从根节点开始执行指令，我们可以通过递归找到要修改的节点，然后从下往上更新经过的所有节点（时间复杂度 $O(logn)$ ）
我们如果更改点 $1$ ，需要更改的节点如图红圈部分：
$$\scriptsize\textcolor{grey}{更改点1}$$
void change(int x,int u,int a){
if(t[x].l==t[x].r){//找到目标更改
t[x].sum=a;
return;
}
int mid=(t[x].l+t[x].r)>>1;//区间中点
if(mid>=u)change(x*2,u,a);//u属于左半部分
else change(x*2+1,u,a);//u属于右半部分
t[x].sum=t[x*2].sum+t[x*2+1].sum;//刷新值
}
调用入口：change(1,x,a);
单点查询同理，只是不用回溯
int ask(int x,int u){
if(t[x].l==t[x].r)return t[x].sum;//找到目标返回值
int mid=(t[x].l+t[x].r)>>1;//区间中点
if(mid>=u)ask(x*2,u);//u属于左半部分
else ask(x*2+1,u);//u属于右半部分
}
调用入口：ask(1,x);
2.区间查询（基础）
区间查询其实并不难，只要递归执行以下步骤：
- 若 $[l,r]$ 完全覆盖了整个区间，立刻回溯
- 若左子节点与 $[l,r]$ 有重叠部分，递归访问左子节点
- 若右子节点与 $[l,r]$ 有重叠部分，递归访问右子节点
我们如果查询区间 $[2,7]$ ，需要查询的节点如图红圈部分：
$$\scriptsize\textcolor{grey}{查询区间[2,7]}$$
int ask(int x,int l,int r){
if(l<=t[x].l&&r>=t[x].r)return t[x].sum;//完全包含
int mid=(t[x].l+t[x].r)>>1;//区间中点
int sum=0;
if(mid>=l)sum+=ask(x*2,l,r);//访问左半部分
if(mid<r)sum+=ask(x*2+1,l,r);//访问右半部分
return sum;
}
调用入口：ask(1,l,r);
学了这么多，练习一下吧！
例题1
luogu P3374 【模板】树状数组 1
别看这道题题目是树状数组，其实用线段树单点修改，区间查询也是可以的
题目描述
如题，已知一个数列，你需要进行下面两种操作：
-
将某一个数加上 $x$
-
求出某区间每一个数的和
输入格式
第一行包含两个正整数 $n,m$，分别表示该数列数字的个数和操作的总个数。 第二行包含 $n$ 个用空格分隔的整数，其中第 $i$
个数字表示数列第 $i$ 项的初始值。
接下来 $m$ 行每行包含 $3$ 个整数，表示一个操作，具体如下：
-
1 x k含义：将第 $x$ 个数加上 $k$ -
2 x y含义：输出区间 $[x,y]$ 内每个数的和
输出格式
输出包含若干行整数，即为所有操作 $2$ 的结果。
样例#1
输入
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
输出
14
16
提示
对于 $30%$ 的数据，$1 \le n \le 8$，$1\le m \le 10$；
对于 $70%$ 的数据，$1\le n,m \le 10^4$；
对于 $100%$ 的数据，$1\le n,m \le 5\times 10^5$。
code
点击查看代码
```cpp #include$$这个人颓废去了，N年后再更$$