线段树学习笔记

概述

假设要从数组arr[0 ... n - 1]查找某个数组某段区间的最小值，其中数组大小固定，但是数组中的元素可以随时更新。一个简单的解法是遍历数组区间寻找最小值，时间复杂度是$O(n)$，额外空间复杂度$O(1)$，当数据量特别大，查询操作很频繁时，耗时可能不能够满足要求。

另一种做法是通过二维数组求出任意两个点为端点组成的区间的最小值，显然这样的预处理时间复杂度是$O(n^2)$，查询时间复杂度是$O(1)$，而额外的空间复杂度则是$O(n^2)$的，当数据量很大时， 这个空间消耗是庞大的。而如果我们想对这段区间内的任意点进行修改，或对某段子区间进行整体修改，再重新求出最小值，这样的操作十分麻烦，而且这个时间复杂度是不能接受的，所以我们可以使用一种数据结构来解决这类问题。

线段树，它在各个区间保存一条线段（数组中的一段子数组），主要用于高效解决连续区间动态查询问题（只要查询运算符合结合律都可以），它将每一段区间[L, R]都分解为[L, M]与[M + 1, R]左右两个子区间（其中M等于$(L + M) / 2$向下取整，子区间分别表示父区间的左右半区间），直到区间两端点$L == R$时即停止分解。这种数据结构保持进行各种操作的时间复杂度为$O(log_2n)$。

原理

线段树的根节点，即开始区间为[1 , N]，我们可使用递归的方法来逐层分解，并将每段区间均视为一个节点，以[1, 6]为例：先将根节点[1, 6]分解为[1, 3]与[4, 6]分别存有两个区间的两个节点，再将[1, 3]与[4, 6]分别分解为[1, 2]、[3]与[4, 5]、[6]四个节点，最后将[1, 2]与[4, 5]区间分解为[1]、[2]、[4]、[5]这四个节点，过程中每一段子区间节点均与其父区间节点有一条指向父区间节点的边，从而形成一棵二叉树。由于二叉树的特性，对区间对修改以及查询的时间复杂度均为$O(log_2n)$。

由于建树时是将区间平均分称两端，所以我们可以将线段树视为满二叉树，将缺少的节点用空区间补全，再对所有节点进行编号，我们就能得到一棵根节点编号为1且当节点号为n时其子节点编号分别为$2 \times n$与$2 \times n + 1$的满二叉树。

所以我们可以使用数组来模拟树形结构，对于每个节点$R$，其左子节点为$2 \times R$，其右子节点为$2 \times n$。这里我们可以通过位运算的方式将常数进行优化，将左子节点写为R << 1，右子节点写为R << 1 | 1（根节点序号须为1）。线段树所需要的节点个数为，所以我们一般把节点数开到四倍，例如int minv[N << 2]。

当对区间进行单点修改时，我们可以发现线段树对每一层只有一个节点包含修改的单点，所以修改某一节点后只需要向上每层更新一个节点的信息即可使整个线段树的信息均为正确的。可以很容易的知道单点修改的时间复杂度为$O(log n)$。

当我们需要对线段树进行区间查询时，根据定理：

n>=3时，一个[1,n]的线段树可以将[1,n]的任意子区间[L,R]分解为不超过个子区间。

我们对某一区间[L, R]进行查询时只需要访问不超过个节点，就可以获取到区间[L, R]的信息，实现时间复杂度为$O(log n)$的区间快速查询。

线段树的区间修改是对某一区间进行整体修改，这里需要引入一个延迟标记来记录对区间的修改信息，这个标记称为懒惰标记(Lazy Tag)。这个标记的含义是：当前节点的信息已经根据标记更新完毕，但当前节点的子节点仍需要进行更新。例如：假设线段树维护的区间和，我们要对某一含有八个数的节点进行区间+3，我们需要对待更改的区间进行+3并给p当前节点标记一个+3的Lazy Tag，然后递归的将当前节点的子节点进行如上的处理，并删除当前节点的Lazy Tag，最后进行向上更新信息，就可以使整个线段树得到正确的结果。而有的标记会相互影响，所以比较简单的处理方法是，每递归到一个区间，首先下推标记（若本节点有标记），然后打上新的标记，这样对每个区间操作对复杂度仍为$O(log n)$。

代码实现

//区间最小值
const int N = 1000;
int a[N];
const int INF = 1e9 + 7;
Struct Segment_Tree {
#define lson (o << 1)
#define rson (o << 1 | 1)
    int minv[N << 2], addv[N << 2];
    inline void pushup(int o) {minv[o] =min( minv[lson],  minv[rson]);}
    inline void pushdown(int o) {
        if(!addv[o]) return;
        addv[lson] += addv[o]; addv[rson] += addv[o];
        minv[lson] += addv[o]; minv[rson] += addv[o];
        addv[o] = 0;
    }
    inline void build(int o, int l, int r) {
        addv[o] = 0;
        if(l == r) {minv[o] = a[l]; return;}
        int mid = (l + r) >> 1;
        build(lson , l, mid); build(rson, mid + 1, r );
        pushup(o);
    }
    inline void optadd(int o, int l, int r, int ql, int qr, int v) { 
        if(ql <= l && qr >= r) {minv[o] += v; addv[o] += v; return;}
        int mid = (l + r) >> 1;
        pushdown(o);
        if(ql <= mid) optadd(lson, l, mid, ql, qr, v);
        if(qr > mid) optadd(rson, mid + i, r, ql, qr, v);
        pushup(o);
    }  
    inline int querymin(int o, int l, int r, int ql, int qr) {
        if(ql <= l && qr >= r) return minv[o];
        int mid = (l + r) >> 1, ans = INF;
        pushdown(o);
        if(ql <= mid) ans = min(ans, querymin(lson, l, mid, ql, qr));
        if(qr > mid) ans = min(ans, querymin(rson, mid + 1, r, ql, qr));
        return ans;
    }
    inline change(int o, int l, int r, int q, int v) {
        if(l == r) {minv[o] += v; return;}
        int mid = (l + r) >> 1;
        if(q <= mid) change(lson, l, mid, q, v);
        else change(rson, mid + 1, r, q, v);
        pushup(o);
    }
};