zkw线段树

2022-03-17 算法

建树
区间查询
单点修改
区间修改的zkw线段树

zkw线段树的功能与普通的线段树完全一致，只是通过魔改略微减小常数，大大减少码量。

线段树是一种较为复杂的数据结构，系统的学习最好结合图文教程。笔者糟糕的美学素养与不过关的美工能力并不足以应付制作图文教程的工作，所以本文并不是zkw线段树的教程，只是贴出各部分地代码并简述原理，充当类似学习笔记的功能~~也就是说懂的都懂不懂的说了也没用~~。

首先，zkw是什么？zkw是张昆玮先生的诨名，他是目前中文互联网上公认的第一个将下面的非递归型线段树整理出来并发表的人，所以被这种非递归型线段树也被称为“zkw线段树”。

建树

zkw线段树是一棵满二叉树：它的叶子结点的深度相等，即相同长度的区间存在了二叉树的同一层中。这样做的好处是可以快速地找到需要查询或修改的元素（即元素在原序列中的编号加上线段树非叶结点的个数），然后再逐层向上修改，直到根节点。

这样做就需要保证线段树叶结点的数量不小于序列中的元素个数。由于在满二叉树中，叶结点的数量都是二的次幂，可能会出现叶子这一层中有的结点为空的情况，但是不影响。为防止出现奇怪的问题，一般建树的时候甚至还会刻意在底层多留几个空位出来。

void build(int n, int seg_tree[], int a[])//a：需要维护的序列；n：a[]的元素个数
{
    int upper_sum = 1 << __lg(n + 5) + 1; //线段树非叶结点数量。叶节点从upper_sum+1开始。+5是留出空位防止笔误
    int i;
    //将需要维护的序列a的元素存入线段树的叶中
    for (i = 1; i <= n; i++)
        seg_tree[i + upper_sum] = a[i];
    //每个非叶结点的值都是它的左右子节点的值之和。从大到小加是因为刚刚初始化的叶节点在树中编号最大
    for (i = upper_sum - 1; i; i--)	
        seg_tree[i] = seg_tree[i << 1] + seg_tree[i << 1 | 1];
}

__lg()是编译器内置函数，__lg(x)的值等于 $\lfloor log_2x \rfloor$ ，不能使用的话可以改用cmath库中的log2()函数。

不难想到，upper_sum实际上的值是线段树中非叶结点的数目加上1，而序列存储又是从第upper_sum + 1个结点开始，这是为了留空编号为upper_sum的结点以防后续操作出错。由于第upper_sum个结点是留空的，将倒数第二行for (i = upper_sum - 1; i; i--)改成for (i = upper_sum; i; i--)并不影响答案（实际上也有很多人就是这么写的）。有计划的留空提高了代码的容错性。

区间查询

为方便边界判断，一般会将区间[l, r]的查询转化为区间(l-1, r+1)的查询来处理。

首先找到l-1和r+1对应的叶结点，设为查询的左右边界lb, rb（注意这就是上述的开区间的两个端点）。将lb和rb一直往它们的祖先方向迭代，直到它们的值相差1（即它们表示的开区间形成了空区间）。由于lb和rb表示的是开区间的端点，每一次，如果lb是它的父节点的左节点或者rb是它的父节点的右节点，那么它们的兄弟结点是就是查询中包含的点，应当将这个兄弟结点的值加到结果中；否则就代表以它们各自的父节点为根的这棵子树中的点都未包含在查询中，不加。由于是满二叉树，编号为奇数的结点都是右子节点，编号为偶数的结点都是左子节点，zkw线段树区间查询的代码极短。

int query(int l, int r, int upper_sum) //计算原序列区间[l,r]上的值
{
    int ret = 0;
    //初始化lb、rb并设定退出条件、迭代方式
    for (int lb = l - 1 + upper_sum, rb = r + 1 + upper_sum; rb - lb > 1; lb >>= 1, rb >>= 1)
    {
        if (~lb & 1) //若lb是偶数，即lb是左儿子
            ret += seg_tree[lb ^ 1];
        if (rb & 1) //若rb是奇数，即rb是右儿子
            ret += seg_tree[rb ^ 1];
    }
    return ret;
}

单点修改

如果需要将序列的某个值加上x，只要修改它在线段树中对应的结点，然后将变化向上传递就行了。

void add(int pos, int x) //将第pos个值加上x
{
    for (int i = k + pos; i; i >>= 1)
        stree[i] += x;
}

区间修改的zkw线段树

一旦涉及到区间修改，事情总会变得麻烦起来。

首先需要讲的是永久化的lazytag。

在普通的线段树中进行区间修改用到了lazytag，表示当前区间修改的值，通过这个标记实现延迟操作，只在每次查询的时候将标记下传。lazytag的下传又是一个递归过程，而zkw线段树贵在它的非递归结构，如果像之前那样使用lazytag就没有意义了。

zkw使用了标记永久化来解决这个问题。所谓标记永久化，就是不将标记下传，只是在查询的途中将lazytag对应的值加上。

在下面，永久化的标记还是成为lazytag。lazytag[i]的意思是：当前时间点下，以结点i为根的子树中的各叶结点仍需相较于初始值变化的值。在区间修改的过程中会改变一些结点的值，而lazytag的用处就是记录那些应当修改，但未被修改的结点的值，在查询的时候加上就行了。

每次区间修改的步骤跟区间查询差不多：将待修改的闭区间[l, r]转化为(l-1, r+1)进行操作，设待操作区间左端点为lb，右端点为rb。每次操作时，如果lb是它的父节点的左节点或者rb是它的父节点的右节点，那么它们的兄弟结点是就是待处理中包含的点，应当将它们（指兄弟节点）的加上对应的值，同时将lazytag加上增加的值；否则就代表以它们各自的父节点为根的这棵子树中的点都未包含在查询中，不修改。这里“对应的值”指的是该节点对应的区间长度乘以增加的值。

同样只用循环到rb-lb=1时退出，但这并不是全部，因为在结束点之上的那些结点的值实际上也改变了。因此需要更新上述循环结束点到根结点之间的所有结点值。下面是区间修改的代码

int lazytag[];
void internal_add(int l, int r, int x, int upper_sum)
{
    int lb = l - 1 + upper_sum, rb = r + 1 + upper_sum, lenl = 0, lenr = 0;
    for (int len = 1; rb - lb > 1; lb >>= 1, rb >>= 1, len <<= 1)
    {
        //先修改当前遍历到节点所代表的区间的值
        seg_tree[lb] += lenl * x, seg_tree[rb] += lenr * x;
        //判断兄弟结点是否为左/右儿子并修改
        if (~lb & 1)
        {
            seg_tree[lb ^ 1] += len * x;
            lazytag[lb ^ 1] += x;
            lenl += len;
        }
        if (rb & 1)
        {
            seg_tree[rb ^ 1] += len * x;
            lazytag[rb ^ 1] += x;
            lenr += len;
        }
    }
    //更新从循环结束点到根的所有结点值
    while (lb)
    {
        seg_tree[lb] += lenl * x, seg_tree[rb] += lenr * x;
        lb >>= 1, rb >>= 1;
    }
}

由于引入了lazytag，区间查询的时候，在访问到一个结点时，也应当加上它的lazytag的值（重复一遍：lazytag[i]指以第i个点为根的子树的叶节点均未修改的值）

int internal_query(int l, int r)
{
    int ret = 0, lb = l - 1 + upper_sum, rb = r + 1 + upper_sum, lenl = 0, lenr = 0;
    for (int len = 1; rb - lb > 1; lb >>= 1, rb >>= 1, len <<= 1)
    {
        ret += lenl * lazytag[lb] + lenr * lazytag[rb];//!
        if (~lb & 1)
        {
            ret += seg_tree[lb ^ 1];//?
            lenl += len;
        }
        if (rb & 1)
        {
            ret += seg_tree[rb ^ 1];//?
            lenr += len;
        }
    }
    while (lb)
    {
        //从结束点到根之间的结点的叶结点的变化可能未考虑，需要加上lazytag
        ret += lazytag[lb] * lenl + lazytag[rb] * lenr;
        lb >>= 1, rb >>= 1;
    }
    return ret;
}

这里有两个问题：感叹号处在干什么？既然lazytag[i]指以第i个点为根的子树的叶节点均未修改的值，为什么打了问号的那两个地方不需要再加上相应lazytag对应的值？

笔者靠硬想没能想出这两个问题的答案。但对于第二个问题如果已知这里不需要加，而lazytag的值又确实需要加上去，那么就说明它一定在其它的某处被加上了。这个“其他的某处”要么在它的子孙方向，要么在它的祖先方向。分析上面的代码不难知道，需要进行问号处的这些操作的点的子孙必然是都没有访问过的，那么加的过程肯定就是在它们的祖先方向上进行的了。而进行了上述步骤之后的一次循环中，l跟r成了最后一次操作点的父节点，在上面的感叹号处，又正好加上了它们的lazytag对应的值。这样，两个问题就都解决了。