zkw线段树

算法总结

（虽然是旧时代的东西了，但是拿出总结总结还是可以的）

介绍#

zkw线段树是线段树的一种非递归实现，比递归版高效，并且引出了更多关于线段树的性质。

标号#

假设我们要为某个长度为 \(N\) 的序列 \(a_i , (0 \le i < N)\) 维护一些区间信息，先令 \(m = 2^{\lceil\log_2{N}\rceil}\)，建立有 \(m\) 个叶子的线段树，显然是个满二叉树。将根节点标号为 \(1\)，记其深度为 \(0\)；然后从浅到深，接着上一层的标号，依次为每一层连续标号。这样开个 \(2 m\) 长的数组就能存下整棵树了。

会发现这样的标号相当于每个节点的左儿子标号是自己的2倍，右儿子则是左儿子的标号加个1；用二进制表示就是左移1位，是左儿子，再或个1，是右儿子。自己的父亲的标号也就可以通过自己的标号除以2获得，即直接右移1位。而又因为每一层是接着上一层的 \(2^i - 1\) 开始标号的，每一层最左边的节点就是 \(2^i\)，最右边就是 \(2^{i+1}-1\)。二进制来看就相当于这一层的最高位的1都在同一位，删掉这一位的1，这一层的标号就相当于从0开始标到 \(2^i - 1\)。那么最左边的叶子标号也就是 \(2^{\lceil\log_2{N}\rceil} = m\)。

由于有了上面的这些性质，想要定位到原来序列的元素 \(a_i\) 对应的叶子就比较容易了，给 \(i\) 加个 \(m\) 就好了，即是说 \(a_i\) 对应的叶子节点的标号是 \(i + m\)。如果想要从深到浅地遍历祖先，不断右移标号就行。

线段树操作#

平常我们使用线段树，都是叶子存 \(a_i\)，让其它节点存储其下连到的所有叶子的区间信息。那么对于线段树的单点操作，就是修改叶子节点并维护祖先节点的信息；而对某个区间 \([l, r): 0 \le l, r < N\) 的操作，就是找刚好被这个区间覆盖的所有节点，然后再处理对应子区间的信息。

单点修改+区间查询#

建树#

由于zkw线段树标号是连续的，可以直接从大到小遍历节点完成树的建立。比如假设叶子节点已经存好值了，用 seg[i] 维护区间和：

1
2
3
4
5
6
7
const int m = 1 << 17;
long long seg[m << 1];

void build() {
    for(int i = m - 1; i > 0; --i)
        seg[i] = seg[i << 1] + seg[(i << 1) | 1];
}

单点修改#

接着上面的例子，如果只是对单点 \(a_i\) 进行修改，由于叶子节点很好定位，父节点遍历也很方便，实现起来很简单：

1
2
3
4
5
6
void modify(int k, int v) {
    k += m;
    seg[k] = v;
    for(; k > 0; k >>= 1)
        seg[i] = seg[i << 1] + seg[(i << 1) | 1];
}

区间查询#

在zkw线段树上，我们可以很容易得到操作区间 \([l, r)\) 对应叶子节点所在的区间 \([l + m, r + m)\)。但线段树不是直接修改这个区间里的所有节点，而是往祖先上走，找到刚好盖住这些叶子的分支节点。

记一对左右指针 \(u, v\)，分别指向 \(u \gets l + m\)，\(v \gets r + m\)。我们试着一直让两个指针在同一层，慢慢地往祖先移动，然后逐层得到所需的分支结点。

若左指针 \(u\) 指向的是其父节点的左儿子，即 \(u\) 是偶数，那么父节点所覆盖的区间的左边界和 \(u\) 指向的节点是一样的，这样 \(u\) 指向的节点并不是我们需要的分支结点；若 \(u\) 指向的是右儿子，即 \(u\) 是奇数，那他父亲所覆盖的区间的左边界就超出我们所需的区间了，那 \(u\) 节点就是我们所需的节点之一，它所覆盖的所有节点都是在我们操作区间内的节点，那我们就在 \(u\) 节点上处理一下区间信息。
接下来移动到浅一层，若 \(u\) 是偶数，直接除以2、指向父节点就行；若 \(u\) 是奇数，\(u\) 节点所覆盖的区间信息我们已经处理了，那我们需要让 \(u\) 指向含有右边区间的信息的节点，而 \(u\) 和 \(u + 1\) 作为同一层相邻的两个节点，刚好覆盖的也是相邻两个区间的信息，所以我们让 \(u\) 自增，然后再指向自增后的父节点，就完成了 \(u\) 指针的转移。

同样地，对于右指针 \(v\)，由于它指向的是区间的开的右边界，所以和 \(v\) 同一层的节点 \(v - 1\) 才是盖到操作区间的节点。类似左指针的讨论，若 \(v\) 是偶数，那么 \(v - 1\) 的开的右边界等于 \(v\) 的闭的左边界，\(v\) 的父亲的左边界和 \(v\) 是相同的，所以不需要在这一层为右指针进行操作；若 \(v\) 是奇数，那么父节点的左边界就变掉了，而 \(v - 1\) 刚好是覆盖我们操作区间右边的一块信息，那么 \(v - 1\) 就是我们所需的分支结点，在 \(v - 1\) 上处理一下区间信息。
转移到浅一层时，若 \(v\) 是偶数，则直接除以2，若 \(v\) 是奇数，自减与否父节点是不变的，可以直接除以2（实现上可以自减一下，因为需要 \(v - 1\) 的值）。这样就完成了 \(v\) 指针的转移。

由于 \(u\) 和 \(v\) 分别指向闭的左边界和开的右边界，所以正常情况下 \(u < v\)，那当 \(u >= v\) 时，显然我们已经遍历了所有需要处理信息的节点，这时迭代就可以结束了。

还是之前的例子，查询区间 \([l, r)\) 上的和：

1
2
3
4
5
6
7
8
9
10
11
long long query(int l, int r) {
    // Query sum of a_l, ..., a_{r-1}
    long long ans = 0;
    for(int u = l + m, v = r + m; u < v; u >>= 1, v >>= 1) {
        if(u & 1)
            ans += seg[u++];
        if(v & 1)
            ans += seg[--v];
    }
    return ans;
}

区间修改+单点查询#

假如我们想维护一个序列，支持一个区间的所有元素加一个数，支持求某一位置的值。那么我们的节点可以用来存对应区间的总的变化量，单点查询就是将叶子及其祖先所有的值加起来。建树的话分支节点清空成0就行，其它操作的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void modify(int l, int r, int d) {
    // Add d to a_l, ..., a_{r-1}
    for(int u = l + m, v = r + m; u < v; u >>= 1, v >>= 1) {
        if(u & 1)
            seg[u++] += d;
        if(v & 1)
            seg[--v] += d;
    }
}

long long query(int k) {
    long long ans = 0;
    for(k += m; k > 0; k >>= 1) {
        ans += seg[k];
    }
    return ans;
}

如果是想让某个区间的所有值都等于一个数，分支节点可以存值的同时，存一下时间戳，查询查祖先链上最新的值就行。

这一类的标记的设计经常被称作是标记永久化。

区间修改+区间查询#

非递归线段树有一个问题，它是自底向上的，但是我们通常的懒惰标记都是需要下传的，即需要自顶向下。那zkw线段树如何解决这一类问题呢？

标记下传+信息收集#

我们观察一下没有需要下传的标记时，区间修改的那些节点有什么的规律。先考虑我们之前区间修改的右指针，为了实现上好看一点，我们往祖先上转移时自减了一下，但是本来右指针指向的就是右儿子，自减和不自减的祖先是一样的。所以叶节点 \(r + m\) 的所有祖先也是我们右指针需要处理区间信息的节点的祖先。那如果我们先直接在这一条祖先链上自顶向下地下传标记，我们不就完成了正常线段树右半部分节点下传标记的工作了？实现时可以使用 \(r + m\) 的所有二进制前缀，就能自顶向下地遍历祖先了。

对于左半部分的节点，如果我们定义一个假的左指针为 \(u’ \gets l + m - 1\)，维护 \(u’\)，使得 \(u’\) 所指的节点的开的右边界是 \(u\) 节点的左边界。当 \(u’\) 是偶数时，相当于原来的左指针 \(u = u’ + 1\) 节点是右儿子，是我们需要处理的节点，\(u\) 和 \(u’\) 同时自增，再转移至祖先；\(u’\) 是奇数时，\(u\) 不是我们需要的节点，两个都转移至祖先继续操作。会发现 \(u’\) 和 \(v\) 一样，自增不自增的父亲、甚至是祖先都一样的，而观察操作的过程会发现 \(u’\) 走过的祖先链的儿子包括了所有 \(u\) 需要处理的节点。因此在叶节点 \(l - 1 + m\) 的祖先链上，自顶向下地下传标记就完成了左半部分的下传标记。

这时，我们已经保证所有我们需要做区间修改的节点的所有父亲都把标记传给了儿子。同时，由于我们是从祖先上沿着一条连续的链进行处理，所以可以保证所有需要得到父亲标记的节点都正确地按拓扑序处理好了。

最后，当我们处理完所有区间的节点，还需要更新它们的祖先的信息，这个时候需要自底向上地处理。那么只需要自底向上地更新叶子 \(l - 1 + m\) 和 \(r + m\) 的祖先链的信息就好，相当于一次单点修改。

实现#

下面以区间加一个数，区间查总的和为例，实现zkw线段树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
const int bc = 18, m = 1 << bc;
long long seg[m << 1], tag[m << 1];

inline void setTag(int u, int d, int l) {
    seg[u] += d * (long long)l;
    tag[u] += d;
}

inline void collect(int u) {
    seg[u] = seg[u << 1] + seg[(u << 1) | 1];
    tag[u] = 0;
}

void build() {
    for(int i = m - 1; i > 0; --i)
        collect(i);
}

void propagate(int leaf) {
    if(leaf < m || leaf - m >= m) // Not a leaf
        return;
    for(int i = bc, l = m, u; i > 0; --i, l >>= 1) {
        u = leaf >> i;
        if(tag[u]) {
            setTag(u << 1, tag[u], l >> 1);
            setTag((u << 1) | 1, tag[u], l >> 1);
            tag[u] = 0;
        }
    }
}

void upgrade(int k) {
    if(k < m || k - m >= m) // Not a leaf
        return;
    for(k >>= 1; k > 0; k >>= 1)
        collect(k);
}

void modify(int l, int r, int d) {
    // Add d to a_l, ..., a_{r-1}
    propagate(l - 1 + m);
    propagate(r + m);
    for(int u = l + m, v = r + m, w = 1; u < v; u >>= 1, v >>= 1, w <<= 1) {
        if(u & 1)
            setTag(u++, d, w);
        if(v & 1)
            setTag(--v, d, w);
    }
    upgrade(l - 1 + m);
    upgrade(r + m);
}

long long query(int l, int r) {
    // Query sum of a_l, ..., a_{r-1}
    propagate(l - 1 + m);
    propagate(r + m);
    long long ans = 0;
    for(int u = l + m, v = r + m; u < v; u >>= 1, v >>= 1) {
        if(u & 1)
            ans += seg[u++];
        if(v & 1)
            ans += seg[--v];
    }
    return ans;
}

总结#

以上就是zkw线段树大致的思路以及实现，相比递归版，少了递归栈，但依然可以处理大部分递归的线段树的任务，并且更加高效。

边界问题#

现在再回头看一些小细节，比如区间的左边界是 \(0\)，或者开的右边界是 \(m\)，会出现什么事情呢？左边界是 \(0\)，叶子也就是 \(m\)，祖先链永远都是某个节点的左儿子，区间操作时除非是根，否则不会去进行操作；右边界是 \(m\)，那这个叶子并不存在，但可以认为这是一个比叶子还深的一个节点，那么在比较时 \(v\) 永远是大于 \(u\) 的，除非 \(u\) 指向了某一层最右边的节点，由于这是个某个节点的右儿子，处理完后会自增，变到下一层，然后就有 \(u=v\)，遍历就结束了。如果这两个条件同时成立，会发现直到 \(u=1\), \(v=2\) 时，会处理一下根的信息，然后转移至浅一层的时候有 \(u=v=1\)，就结束了。因此上面给出的实现是完全可以处理边界的情况的。

Trie#

如果把zkw线段树看作是字符集为 \({0,1}\) 的 Trie，会发现标号的二进制就是前缀多个 1 的 Trie 对应的字符串。

树状数组#

如果在线段树上倒着从第 \(N\) 个叶节点，将叶节点及其所有的祖先标同一个号，标过的祖先不给标，我们得到的实际就是树状数组（Fenwick Tree），这也是为什么很多人称之为没有右儿子的线段树。

zkw线段树相比于树状数组，用了更多的空间，常数还更大；但是树状数组没有办法在 \(\mathcal{O}{(\log{n})}\) 时间内解决没有区间减性质的问题，比如单点修改，求区间最大值（网传的做法的时间复杂度应该是 \(\mathcal{O}{(\log^2{n})}\) 的，每次往前走 \(\log\) 层，然后减一，再继续走，最多走 \(\log\) 次；也可以通过计数发现复杂度不是 \(\mathcal{O}{(\log{n})}\)），zkw线段树则可以很正常地处理只有区间和性质的问题。其次，zkw线段树可以有懒惰标记等等的东西，可以比树状数组多处理一些问题。

其它#

再有一点，由于需要修改的节点标号可以预先确定，并且只有 \(\mathcal{O}{(\log{n})}\) 个，可持久化，或者简单的回退操作都可以很轻松地使用zkw线段树完成。

zkw线段树好处就是不需要记录左右儿子的指针，这样对应的缺点也很明显，它是连续标号的，不能够离散化位置的序列就不可以用zkw线段树处理了，节点开不了那么多。这样想要处理区间问题还是随用随开空间的递归版线段树好一些。

总之，zkw线段树是线段树的一种高效的非递归实现，在比赛中还是很实用的（好调）。不过，它只是实现，对于具体的问题，还需要多考虑如何构建线段树，节点需要维护哪些信息等等的问题。这样才能自如地使用各种各样的实现，让线段树成为自己强大的武器。

#算法 #数据结构 #总结 #线段树
BCPC2017 预赛 E. 气球派对 AtCoder Regular Contest 084

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×