线段树 学习笔记

Part 1. 线段树简介

线段树是算法竞赛中常用的用来维护区间信息的数据结构。
线段树可以在 \(O(\log n)\) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

线段树的操作和树状数组很相似，不过线段树可以干一些树状数组干不了的，但后者更快些。

线段树可以看作是一棵满二叉树，尽管有些节点是空的。

（图片来源于网络）

根据完全二叉树的性质，\(i\) 的左儿子就是 \(i \times 2\)，右儿子就是 \(i \times 2+1\)。

Part 2. 建树（build）

首先我们得对要操作的序列建树，才能进行更多操作。

由于完全二叉树的性质，可以直接用一个一维数组存线段树。

特别注意，线段树数组要开 \(4\) 倍的空间，至于为什么，画一个序列长度 \(10\) 的线段树就知道了。

int a[MAXN];
int tree[MAXN << 2];
inline int ls(int p) { return p << 1; }//左儿子
inline int rs(int p) { return p << 1 | 1; }//右儿子
inline void push_up(int p) { tree[p] = tree[ls(p)] + tree[rs(p)]; }//由左右儿子来更新当前区间的值
void build(int p, int l, int r) {
    if (l == r) { tree[p] = a[l]; return; }
    int mid = l + r >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    push_up(p);//回溯时才更新
}

push_up 很灵活，这里实现的是区间求和，所以将左右区间加起来，当然可以改成最小值或最大值也没问题。

根据这个特性，我们发现线段树只能维护满足结合律的东西。

Part 3. 更新（update）

线段树的更新非常特别，用了一个叫懒标记（Lazy tag）的东西。

其思想是，当用到这个节点时，才去更新，而不是一来就更新（不然一样很慢）。

void push_down(int p, int l, int r) {
    int mid = l + r >> 1;
    tag[ls(p)] += tag[p];
    tree[ls(p)] += (mid - l + 1) * tag[p];
    tag[rs(p)] += tag[p];
    tree[rs(p)] += (r - (mid + 1) + 1) * tag[p];
    tag[p] = 0;
}
void update(int ql, int qr, int l, int r, int p, int k) {
    if (ql <= l && r <= qr) {
        tag[p] += k;
        tree[p] += (r - l + 1) * k;
        return;
    }
    push_down(p, l, r);
    int mid = l + r >> 1;
    if (ql <= mid)update(ql, qr, l, mid, ls(p), k);
    if (qr > mid)update(ql, qr, mid + 1, r, rs(p), k);
    push_up(p);
}

个人认为，push_down 操作是线段树最优美的操作，一开始比较难理解，很正常。

特别注意：push_down 操作仅适用于（大概吧）区间求和类的问题，对于求区间最小最大值的，不要使用 push_down！

Part 4. 查询（query）

查询的代码和更新类似。

int query(int ql, int qr, int l, int r, int p) {
    if (ql <= l && r <= qr) { return tree[p]; }
    push_down(p, l, r);//记得，用到该节点时要 push_down
    int mid = l + r >> 1;
    int res = 0;
    if (ql <= mid)res += query(ql, qr, l, mid, ls(p));
    if (qr > mid)res += query(ql, qr, mid + 1, r, rs(p));
    return res;
}

特别注意：query 操作需要 push_down，但不需要 push_up。

Part 5. 高清无码标程

线段树的模板：

int a[MAXN];
int tree[MAXN << 2], tag[MAXN << 2];
inline int ls(int p) { return p << 1; }
inline int rs(int p) { return p << 1 | 1; }
inline void push_up(int p) { tree[p] = tree[ls(p)] + tree[rs(p)]; }
void build(int p, int l, int r) {
    if (l == r) { tree[p] = a[l]; return; }
    int mid = l + r >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    push_up(p);
}
void push_down(int p, int l, int r) {
    int mid = l + r >> 1;
    tag[ls(p)] += tag[p];
    tree[ls(p)] += (mid - l + 1) * tag[p];
    tag[rs(p)] += tag[p];
    tree[rs(p)] += (r - (mid + 1) + 1) * tag[p];
    tag[p] = 0;
}
void update(int ql, int qr, int l, int r, int p, int k) {
    if (ql <= l && r <= qr) {
        tag[p] += k;
        tree[p] += (r - l + 1) * k;
        return;
    }
    push_down(p, l, r);
    int mid = l + r >> 1;
    if (ql <= mid)update(ql, qr, l, mid, ls(p), k);
    if (qr > mid)update(ql, qr, mid + 1, r, rs(p), k);
    push_up(p);
}
int query(int ql, int qr, int l, int r, int p) {
    if (ql <= l && r <= qr) { return tree[p]; }
    push_down(p, l, r);
    int mid = l + r >> 1;
    int res = 0;
    if (ql <= mid)res += query(ql, qr, l, mid, ls(p));
    if (qr > mid)res += query(ql, qr, mid + 1, r, rs(p));
    return res;
}