线段树

线段树是用于维护区间信息的一种数据结构，可以在$O(\log n)$的复杂度内实现区间修改，区间查询等操作，还可以维护各种满足结合律的信息。

原理：

线段树的建树：设有数组$a_i,i\in [1,n]$，把一整个数组区间划分为两个子区间，设区间$[l,r]$，那么取区间中点$mid=\lfloor \frac{l+r}{2}\rfloor$，那么区间就会被划分为$[l,mid],[mid+1,r]$，一直递归下去，直到$l=r$，这个过程非常像二叉树，所以我们就用一棵树来记录每个区间。递归到达边界时区间长度为$0$，那么就可以代表一个数组$a_i$，回溯的时候进行合并，这样就能维护数组的信息。与二叉树一样，设节点编号为$u$，那么左儿子的编号就为$2\ast u$，右儿子节点的编号就为$2\ast u+1$，在程序中$2\ast u$可以用u << 1来代替，$2\ast u+1$可以用u << 1 | 1来代替，这样就方便递归建树了。

线段树结构体：

struct Node {
   
    int l, r;
    //需要维护的信息和懒标记
} tr[N << 2];

代码：

void build(int u, int l, int r) {
   
    if (l == r) tr[u] = {
   l, r};
    else {
   
        tr[u] = {
   l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

区间查询：

设$L,R$为查询区间，$tr[u].l,tr[u].r$为节点左右端点，$mid$为节点中点

$①:L,R>mid$ 查询右子树

$②:L\le mid,R>mid$ 查询左右子树

$③:tr[u].l\ge L,tr[u].r\le R$ 直接返回整个区间

$④:L\le mid,R>mid$ 查询左右子树

$⑤:L,R\le mid$ 查询左子树

例如求区间$[l,r]$的和，我们可以通过线段树的性质，合并两个子区间的和来求最终答案，首先子区间必须记录这个信息才可以合并，于是我们就引入了$\text{pushup}$这个操作，来维护向上传递的信息。

区间和的$\text{pushup}:$

void pushup(int u) {
   
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

很好理解，就是总区间的和等于两个子区间的和，那么最初的区间和就是在建树过程中递归边界遍历到区间长度为$0$的区间时记录的，此时$tr[u].sum=a[l]$，所以建树的时候需要在最后$\text{pushup}$

代码：

int ask(int u, int l, int r) {
   
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1, res = 0;
    if (l <= mid) res += ask(u << 1, l, r);
    if (r > mid) res += ask(u << 1 | 1, l, r);
    return res;
}

单点修改：

假设要将$a_{pos}$修改为$c$，那么只需要二分地找到位置$pos$，当$l=r$时，把$a_l$改为$c$，由于修改了单个值，需要重新$\text{pushup}$一下，向上传递更新的信息。

代码：

void modify(int u, int pos, int c) {
   
    if (tr[u].l == pos && tr[u].r == pos) {
   
        tr[u] = {
   l, r, c};
    } else {
   
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) {
   
            modify(u << 1, pos, c);
        } else {
   
            modify(u << 1 | 1, pos, c);
        }
        pushup(u);
    }
}

区间修改：

假设要把区间$[l,r]$的所有数修改为$c$，如果按照常规方法每个数都做单点修改，时间复杂度为$O(n\log n)$，是比较慢的，所以我们可以引入懒标记，用$\text{pushdown}$操作来维护，具体操作就是先对一个区间做一个标记，这个标记表示对这个区间所有数都$+c$，需要用到的时候再用$\text{pushdown}$下传到子节点，懒标记清空。$\text{pushdown}$必须在查询或修改之前就下传，保证答案的正确性。

区间修改、区间和的$\text{pushdown}:$

void pushdown(int u) {
   
    tr[u << 1].add += tr[u].add, tr[u << 1 | 1].add += tr[u].add;
    tr[u << 1].sum += (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].add, tr[u << 1 | 1].sum += (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].add;
    tr[u].add = 0;
}