目录

线段树

算法竞赛> 笔记
2644

线段树

时间复杂度 建树:$O(n)$ 区间查询:$O(logn)$ 区间修改:$O(logn)$

线段树是一种二叉树，比原数组多的节点用来存储对应原数组的某个区间的信息，通过这些节点显著降低了区间查询和修改的时间复杂度，有一些地方是“幽灵节点” ,这些节点从不使用但被编号以保证真节点能通过下标$2p$和$2p+1$访问到子节点，浪费了一些空间，且最大不会超过原数组的大小的4倍。

证明：建树时开4倍原数组大小

线段树的最下层存放的是数组的真实值，所以最下层的节点数为$2^{\lceil \log_2 n \rceil}$，所有节点数量用等比数列求和公式得到 转换为证明$2^{\lceil \log_2 n \rceil + 1} - 1 \leq 4n$

证明： 我们需要证明不等式 $2^{\lceil \log_2 n \rceil + 1} - 1 \leq 4n$。

  1. $\lceil \log_2 n \rceil$ 是 $n$ 的以 2 为底的对数向上取整。 这意味着 $ \lceil \log_2 n \rceil $ 是使得 $2^{\lceil \log_2 n \rceil} \geq n$ 的最小整数。 因此，$\log_2 n \leq \lceil \log_2 n \rceil < \log_2 n + 1$。

  2. 因此，$2^{\log_2 n} \leq 2^{\lceil \log_2 n \rceil} < 2^{\log_2 n + 1}$，即 $n \leq 2^{\lceil \log_2 n \rceil} < 2n$。

  3. 乘以2得到： $2n \leq 2^{\lceil \log_2 n \rceil + 1} < 4n$。

  4. 所以，$2^{\lceil \log_2 n \rceil + 1} \leq 4n$。

  5. 减去1得： $2^{\lceil \log_2 n \rceil + 1} - 1 < 4n$。

因此，得证 $2^{\lceil \log_2 n \rceil + 1} - 1 \leq 4n$。

建树

递归 后序遍历二叉树，建好左右子树后再存根的值为要维护的东西 顺便记录当前节点覆盖的区间长度

懒标记

新建一下数组用于存放懒信息 如果能不更新就不更新，必须更新时只往下更新一层。 为什么懒？只有用到当前节点所覆盖的区间时，才下发懒标记 如何下发，分别清算左，右区间，再分别给左右区间打上懒标记，自身懒标记清除。 为什么效率高？可能多次的修改只需要传递一次，优化常数，（一次传递包括了多次修改）

线段树常见方法一览

void build(l, r, i) : 建树 void up(i..) : 根据子范围的查询信息，把父范围的查询信息更新正确 void down(i..) : 父范围的懒信息，往下只下发一层，给左范围、右范围，然后父范围的懒信息清空 void apply(): 当前范围被修改任务全覆盖时 或 父范围发下来的懒更新时，信息数组们如何修改 void midify(jobl, jobr, jobv, l, r, i) : 范围上修改维护信息 int query(jobl, jobr, l, r, i) : 范围上的信息查询任务

struct LazySegmentTree {
    int n;
    vector<Node> tree;
    vector<Tag> tag;
    LazySegmentTree(const vector<Node>& a, int _n) :n(_n), tree(4 << __lg(n)), tag(4 << __lg(n)) {
        build(a, 1, 1, _n);
    }
    void up(int p) {
        tree[p] = tree[p << 1] + tree[p << 1 | 1];
    }
    void build(const vector<Node>& a, int p, int l, int r) {
        if (l == r) {
            tree[p] = a[l];
            return;
        }
        int m = (l + r) >> 1;
        build(a, p << 1, l, m);
        build(a, p << 1 | 1, m + 1, r);
        up(p);
    }
    void apply(int p, const Tag& v) {
        tree[p].apply(v);
        tag[p].apply(v);
    }
    void down(int p) {
        apply(p << 1, tag[p]);
        apply(p << 1 | 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int ml, int mr, Tag& v, int p, int l, int r) {
        if (ml <= l && r <= mr) {
            apply(p, v);
            return;
        }
        int m = (l + r) >> 1;
        down(p);
        if (ml <= m) modify(ml, mr, v, p << 1, l, m);
        if (mr > m) modify(ml, mr, v, p << 1 | 1, m + 1, r);
        up(p);
    }
    void modify(int ml, int mr, Tag& v) {
        modify(ml, mr, v, 1, 1, n);
    }
    void query(int ql, int qr, int p, int l, int r, Node& res) {
        if (ql <= l && r <= qr) {
            res = res + tree[p];
            return;
        }
        int m = (l + r) >> 1;
        down(p);
        if (ql <= m) query(ql, qr, p << 1, l, m, res);
        if (qr > m) query(ql, qr, p << 1 | 1, m + 1, r, res);
    }
    Node query(int ql, int qr) {
        Node res;
        query(ql, qr, 1, 1, n, res);
        return res;
    }
};

推荐文章

dfs
背包DP