线段树

2021-09-22

如题目＞▽＜

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。

建树前准备

#define ls(x) x << 1 // 左儿子
#define rs(x) x << 1 | 1 //右儿子
long long num[MAX << 2];// 线段树本体（需要四倍空间）
long long a[MAX];// 源数据数组
long long lazy[MAX << 2];// 懒标记

线段树的建立

inline void push_up(ll p) { // 向上更新节点的值
    num[p] = num[ls(p)] + num[rs(p)];
}
inline void build(ll p, ll l, ll r) {
    lazy[p] = 0;
    if (l == r) {// 如果左右区间相同，那么当前必然是叶子节点，真实赋值
        num[p] = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    // 采用二叉树来降低复杂度
    push_up(p);
    // 通过子节点来维护父亲节点，所以应当在回溯时pushup
}

线段树的区间修改

inline void f(ll p, ll l, ll r, ll k) {
    num[p] += (r - l + 1) * k;
    lazy[p] += k;
    // 区间统一进行修改，懒标记加上k，节点值加上节点长度*k（区间每个数同时加上k）
}
// f函数用于更新当前节点所代表的区间
inline void push_down(ll p, ll l, ll r) {
    ll mid = (l + r) >> 1;
    f(ls(p), l, mid, lazy[p]);
    f(rs(p), mid + 1, r, lazy[p]);
    lazy[p] = 0;
    // 每次更新两个儿子节点，向下传递懒标记（注意将本节点的懒标记清零）
}
inline void update(ll nl, ll nr, ll l, ll r, ll p, ll k) {
    // nl, nr为要修改的区间
    // l, r, p为当前节点的区间断点以及节点编号
    if (nl <= l && nr >= r) {// 要修改的区间包含该节点，进行更新
        f(p, l, r, k);
        return;
    }
    ll mid = (l + r) >> 1;
    // 下一次递归点，要向下更新节点
    push_down(p, l, r);
    if (nl <= mid) {
        update(nl, nr, l, mid, ls(p), k);
    }
    if (nr > mid) {
        update(nl, nr, mid + 1, r, rs(p), k);
    }
    // 回溯时要向上更新节点值
    push_up(p);
}

线段树的区间查询

inline ll query(ll x, ll y, ll l, ll r, ll p) {
    ll res = 0;
    if (x <= l && y >= r) {// 查找的区间包含该节点，直接返回该节点的值
        return num[p];
    }
    ll mid = (l + r) >> 1;
    // 一定不要忘了查询时也要向下更新节点，因为有的懒标记有可能没有完全覆盖需要查询的区间，所以要进行更新
    push_down(p, l, r);
    if (x <= mid) {
        res += query(x, y, l, mid, ls(p));
    }
    if (y > mid) {
        res += query(x, y, mid + 1, r, rs(p));
    }
    return res;
}

好用的一键打包式线段树

// 这两个宏不能忘了
#define ls(x) x << 1
#define rs(x) x << 1 | 1

struct Tree {
    ll l, r, sum, len;
} tree[MAX << 2];
void push_up(ll p) {
    ll l = tree[p].l, r = tree[p].r;
    if (tree[p].sum) {
        tree[p].len = X[r + 1] - X[l];
    } else {
        tree[p].len = tree[ls(p)].len + tree[rs(p)].len;
    }
}
void build(ll p, ll l, ll r) {
    tree[p].l = l, tree[p].r = r;
    tree[p].len = 0;
    tree[p].sum = 0;
    if (l == r) {
        return;
    }
    ll mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
}
void update(ll p, ll L, ll R, ll k) {
    ll l = tree[p].l, r = tree[p].r;
    if (X[l] >= R || X[r + 1] <= L) {
        return;
    }
    if (X[l] >= L && X[r + 1] <= R) {
        tree[p].sum += k;
        push_up(p);
        return;
    }
    update(ls(p), L, R, k);
    update(rs(p), L, R, k);
    push_up(p);
}

几道板题

线段树1：纯纯的模板，上面板子可解
线段树2：添加了个新操作，需要将区间内的数*x，两个懒标记可解。更新值时要注意要先乘再加这样才不会丢失精度