1 线段树
1.1 什么是线段树？
线段树在算法竞赛中常用于区间操作。时间复杂度$O(\log n)$。
1.2 线段树的应用
1.2.1 线段树的基本应用
顾名思义，区间修改，区间查询。
1.2.2 线段树最大字段和问题上的运用
问题描述：
为了解决这个问题，我们需要引入的懒标记有如下几个
- $maxv$ 区间最大子段和，也就是问题的答案。
- $sumv$ 区间的和。
- $maxnl$ 包含左端点的区间最大子段和。
- $maxr$ 包含右端点的区间最大子段和。
在修改时
先更新 $maxv$。
若 $maxl < 0 \and maxr < 0$（情况一），$maxv = \max{maxl,maxr}$ 。题目中要求必须要取一个元素，不能不取。
若情况一不成立，则说明 $maxl < 0 \or maxr < 0$ 为真（情况二），此时需要将 $maxv$ 归 $0，然后将$ $maxv$ 就可以加上 $maxl,maxr$ 中为正的值。
也有可能以上的情况都不是最大子段和，最后的 $maxv = \max{maxv,maxv(左儿子),maxv(右儿子)}$。特别说明，以上两种情况中的 $maxl$ 和 $maxr$ 分别是其右左儿子的信息。
接着更新 $maxr$ 和 $maxl$ 。
因为线段树需要合并两个区间，可以得出 $maxl$ 为左儿子的 $maxl$ 与左儿子 $sumv$ 和右儿子 $maxl$ 和的最大值。而 $maxr$ 为右儿子的 $maxr$ 与右儿子 $sumv$ 和左儿子 $maxr$ 的最大值。该节点的 $sum$ 为其左右儿子 $sum$ 的和。
在查询时
若查询区间覆盖这一节点，则返回这一节点的信息；若完全覆盖了其中一个儿子，则返回覆盖到的儿子的信息；若没有完全覆盖一个儿子，通过合并的方式查询覆盖到的区间。最后返回的 $maxv$ 即为一次查询的最终答案。
模板题代码
1.2.3 01 区间翻转 + 最长子段和
Code
1.3 利用树状数组代替线段树
众所周知线段树的常数大，代码难写，而在考试中经常出现时间不足从而写不出线段树造成悲剧的情况。但现在，我们可以使用树状数组这种代码好写的数据结构代，完成类似于线段树的区间修改区间查询功能。
为了赋予树状数组这一伟大的使命，我们需要两个树状数组，$t1、t2$。
令 $t[ i ] = a[i] – a[i-1]$ (差分，其中 $a$ 为给定的数组)，易得：
$$\sum_{i=1}^{n} t1[i]=a[n]$$
于是我们可以进行转换：
$$=\sum_{i=1}^{n}a[i] = \sum_{i = 1}^{n}\sum_{j=1}^{i}t1[j]$$
由加法交换律和加法结合律可得：
$$=\sum_{i =1}^{n} t1[i]\times(n-i+1)$$
由乘法分配律可得：
$$=n\times \sum_{i=1}^{n} t1[i]- \sum_{i = 1}^{n}t1[i]\times (i – 1)$$
令 $t2[i] = t1[i]\times(i-1)$ ，最终可以得到：
$$=n\times \sum_{i=1}^{n} t1[i]- \sum_{i = 1}^{n}t2[i]$$
对于一次添加操作：
void modif(int x, int v) {
t2.modify(x, (x - 1) * v); t1.modify(x, v);
}
对于一次查询操作：
int qure(int y) {
return t1.qurey(y) * (y) - t2.qurey(y);
}
那么对于一次区间查询，则有：
int qurey(int l, int r) {
return qure(r) - qure(l - 1);
}
同理，区间修改：
void modify(int l, int r, int v) {
modif(l ,v); modif(r + 1, -v);
}
完整代码
1.4 线段树合并
线段树合并是通过一种相当暴力的手法把两颗线段树的节点合并，常用于维护书图上树上问题。
进行操作需要用到动态开点线段树，有点可持久化的思想。
似乎比较常规，没有什么需要特特别注意的。
合并：
int merge(int a, int b, int l = 1, int r = -1) {
if (r == -1) r = n;
if(!a || !b) return max(a, b);
if(l == r) {
sum[a] += sum[b];
return a;
}
int mid = l + r >> 1;
ls[a] = merge(ls[a], ls[b], l, mid);
rs[a] = merge(rs[a], rs[b], mid + 1, r);
update(a);
return a;
}