2022-7-19

每日一题-线段树

前沿

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。线段树可以在$O(logN)$的时间复杂度内实现单点修改、区间修改、区间查询(区间求和,求区间最大值,求区间最小值)等操作。线段树维护的信息在很多时候可以认为是满足(幺)半群的性质的信息。

一个幺半群$M=(S,\circ,e)$其中$\circ$为在集合$S$上定义的二元运算符,具有如下性质:

  • 封闭性:$\forall x \in S$和$\forall y \in S$有$x \circ y \in S$
  • 结合律:$\forall x,y,z \in S$有$(x\circ y)\circ z = x \circ (y \circ z)$。
  • 存在幺元:$\exists e \in S$满足$\forall x \in S$有$e \circ x = x$,$e$为左幺元,或者反过来为右幺元

我们观察到线段树上的信息一般满足这样的性质,一些数域上的加法与乘法自然,考虑二元的$max(x,y)$ 运算,此时幺元为$-\infty$也满足这样的性质(一般左右幺元相同时简称为幺元)。

基本知识

建树

线段树将每个长度不为1的区间划分成左右两个区间递归求解,把整个线段划分为一个树形结构,通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。

有个大小为5的数组$a = \{10,11,12,13,14\}$,要将其转化为线段树,有以下做法:设线段树的根节点编号为1,用数组d来保存我们的线段树,$d_i$用来保存线段树上编号为i的节点的值(这里每个节点所维护的值就是这个节点所表示的区间总和)。树的状态为如图:

image-20220719150056772

通过观察不难发现, $d_i$的左儿子节点就是$d_{2*i}$,$d_i$的右儿子节点就是$d_{2*i+1}$。如果$d_i$表示的是区间[s,t],那么$d_i$的左儿子节点表示的是区间$[s,\frac{s+t}{s}]$,$d_i$的右儿子表示的是区间 $[\frac{s+t}{s}+1, t]$。建树代码如下:

def build(s, t, p):
    # 对 [s,t] 区间建立线段树,当前根的编号为 p
    if s == t:
        d[p] = a[s]
        return
    m = s + ((t - s) >> 1)
    # 移位运算符的优先级小于加减法,所以加上括号
    # 如果写成 (s + t) >> 1 可能会超出 int 范围
    build(s, m, p * 2); build(m + 1, t, p * 2 + 1)
    # 递归对左右区间建树
    d[p] = d[p * 2] + d[(p * 2) + 1]

关于线段树的空间:如果采用堆式存储,若有n个叶子结点,则d数组的范围最大为$2^{\left\lceil\log{n}\right\rceil+1}$。

区间查询

区间查询,比如求区间[l,r]的总和、求区间最大值/最小值等操作。

仍然以最开始的图为例,如果要查询区间[1,5]的和,那直接获取$d_1$的值即可。

一般地,如果要查询的区间是[l,r],则可以将其拆成最多为$O(logn)$个 极大 的区间,合并这些区间即可求出[l,r]的答案。

区间修改

如果要求修改区间[l,r],把所有包含在区间[l,r]中的节点都遍历一次、修改一次,时间复杂度无法承受。我们这里要引入一个叫做 「懒惰标记」 的东西。懒惰标记,简单来说,就是通过延迟对节点信息的更改,从而减少可能不必要的操作次数。每次执行修改时,我们通过打标记的方法表明该节点对应的区间在某一次操作中被更改,但不更新该节点的子节点的信息。实质性的修改则在下一次访问带有标记的节点时才进行。

仍然以最开始的图为例,我们将执行若干次给区间内的数加上一个值的操作。我们现在给每个节点增加一个 ,表示该节点带的标记值。最开始时的情况是这样的(为了节省空间,这里不再展示每个节点管辖的区间):

image-20220719154022060

现在我们准备给[3,5]上的每个数都加上5。根据前面区间查询的经验,我们很快找到了两个极大区间[3,3]和[4,5](分别对应线段树上的3号点和5号点)。我们直接在这两个节点上进行修改,并给它们打上标记:

image-20220719154121794

我们发现,3号节点的信息虽然被修改了(因为该区间管辖两个数,所以$d_3$加上的数是10),但它的两个子节点却还没更新,仍然保留着修改之前的信息。不过不用担心,虽然修改目前还没进行,但当我们要查询这两个子节点的信息时,我们会利用标记修改这两个子节点的信息,使查询的结果依旧准确。

接下来我们查询一下[4,4]区间上各数字的和。

我们通过递归找到[4,5]区间,发现该区间并非我们的目标区间,且该区间上还存在标记。这时候就到标记下放的时间了。我们将该区间的两个子区间的信息更新,并清除该区间上的标记。

image-20220719154321260

现在6,7两个节点的值变成了最新的值,查询的结果也是准确的。接下来给出在存在标记的情况下,区间修改和查询操作的参考实现。

# 区间修改
def update(l, r, c, s, t, p):
    # [l, r] 为修改区间, c 为被修改的元素的变化量, [s, t] 为当前节点包含的区间, p
    # 为当前节点的编号
    if l <= s and t <= r:
        d[p] = d[p] + (t - s + 1) * c
        b[p] = b[p] + c
        return
    # 当前区间为修改区间的子集时直接修改当前节点的值, 然后打标记, 结束修改
    m = s + ((t - s) >> 1)
    if b[p] and s != t:
        # 如果当前节点的懒标记非空, 则更新当前节点两个子节点的值和懒标记值
        d[p * 2] = d[p * 2] + b[p] * (m - s + 1)
        d[p * 2 + 1] = d[p * 2 + 1] + b[p] * (t - m)
        # 将标记下传给子节点
        b[p * 2] = b[p * 2] + b[p]
        b[p * 2 + 1] = b[p * 2 + 1] + b[p]
        # 清空当前节点的标记
        b[p] = 0
    if l <= m:
        update(l, r, c, s, m, p * 2)
    if r > m:
        update(l, r, c, m + 1, t, p * 2 + 1)
    d[p] = d[p * 2] + d[p * 2 + 1]
# 区间查询
def getsum(l, r, s, t, p):
    # [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p为当前节点的编号
    if l <= s and t <= r:
        return d[p]
    # 当前区间为询问区间的子集时直接返回当前区间的和
    m = s + ((t - s) >> 1)
    if b[p]:
        # 如果当前节点的懒标记非空, 则更新当前节点两个子节点的值和懒标记值
        d[p * 2] = d[p * 2] + b[p] * (m - s + 1)
        d[p * 2 + 1] = d[p * 2 + 1] + b[p] * (t - m)
        # 将标记下传给子节点
        b[p * 2] = b[p * 2] + b[p]
        b[p * 2 + 1] = b[p * 2 + 1] + b[p]
        # 清空当前节点的标记
        b[p] = 0
    sum = 0
    if l <= m:
        sum = getsum(l, r, s, m, p * 2)
    if r > m:
        sum = sum + getsum(l, r, m + 1, t, p * 2 + 1)
    return sum
优化建议

这里总结几个线段树的优化:

  • 在叶子节点处无需下放懒惰标记,所以懒惰标记可以不下传到叶子节点。
  • 下放懒惰标记可以写一个专门的函数 pushdown,从儿子节点更新当前节点也可以写一个专门的函数 maintain(或者对称地用 pushup),降低代码编写难度。
  • 标记永久化:如果确定懒惰标记不会在中途被加到溢出(即超过了该类型数据所能表示的最大范围),那么就可以将标记永久化。标记永久化可以避免下传懒惰标记,只需在进行询问时把标记的影响加到答案当中,从而降低程序常数。具体如何处理与题目特性相关,需结合题目来写。这也是树套树和可持久化数据结构中会用到的一种技巧。
public class SegmentTreeDynamic {
    class Node {
        Node left, right;
        int val, add;
    }
    private int N = (int) 1e9;
    private Node root = new Node();
    public void update(Node node, int start, int end, int l, int r, int val) {
        if (l <= start && end <= r) {
            node.val += (end - start + 1) * val;
            node.add += val;
            return ;
        }
        int mid = (start + end) >> 1;
        pushDown(node, mid - start + 1, end - mid);
        if (l <= mid) update(node.left, start, mid, l, r, val);
        if (r > mid) update(node.right, mid + 1, end, l, r, val);
        pushUp(node);
    }
    public int query(Node node, int start, int end, int l, int r) {
        if (l <= start && end <= r) return node.val;
        int mid = (start + end) >> 1, ans = 0;
        pushDown(node, mid - start + 1, end - mid);
        if (l <= mid) ans += query(node.left, start, mid, l, r);
        if (r > mid) ans += query(node.right, mid + 1, end, l, r);
        return ans;
    }
    private void pushUp(Node node) {
        node.val = node.left.val + node.right.val;
    }
    private void pushDown(Node node, int leftNum, int rightNum) {
        if (node.left == null) node.left = new Node();
        if (node.right == null) node.right = new Node();
        if (node.add == 0) return ;
        node.left.val += node.add * leftNum;
        node.right.val += node.add * rightNum;
        // 对区间进行「加减」的更新操作,下推懒惰标记时需要累加起来,不能直接覆盖
        node.left.add += node.add;
        node.right.add += node.add;
        node.add = 0;
    }
}
最后修改:2022 年 12 月 05 日
如果觉得我的文章对你有用,请随意赞赏