1. 从递归到迭代zkw线段树到底解决了什么问题第一次接触zkw线段树是在一场线上算法赛里当时用传统递归线段树写区间修改TLE了三发赛后看别人的代码发现有人用了一种“非递归、自底向上”的写法代码短得离谱跑得还快。后来才知道这就是zkw线段树由一位国内选手提出的写法核心思路是把整棵树铺成一个完全二叉树的数组形态然后利用叶子节点下标直接定位自底向上完成修改和查询。传统递归线段树的问题在于每次操作都要从根节点一路递归下去函数调用开销大常数高遇到卡常的题目很容易被卡。而zkw线段树把递归展开成循环用位运算代替乘除把常数压到极低。它适合所有需要单点修改区间查询、区间修改区间查询的场景比如区间求和、区间最值、区间染色等问题。如果你已经会写普通线段树但总被常数卡住或者想写出更短更快的代码那这套写法值得花时间吃透。这篇文章我会从原理讲起把建树、单点修改、区间查询、区间修改、标记下传这几个环节全部拆开配上可直接复制的代码再补充几个扩展技巧比如标记永久化、多标记处理、动态开点等。全文基于我自己的实操经验代码都实测过你可以直接拿去用。2. 核心原理拆解为什么zkw线段树能这么快2.1 完全二叉树的数组布局zkw线段树的第一个关键点是把线段树建成一棵满二叉树叶子节点全部在同一层。假设我们要维护的区间长度是n那么取一个比n大的最小2的幂记为N。整棵树用数组tr[]存储叶子节点从下标N开始依次对应原数组的每个元素。也就是说原数组第i个元素从1开始计数对应tr[Ni-1]。这样做的直接好处是任意一个叶子节点的下标可以直接算出来不需要递归查找。父节点和子节点的关系也很简单节点p的左孩子是p1右孩子是p1|1父节点是p1。所有操作都可以用位运算完成速度极快。举个例子n5取N8。原数组a[1..5]对应tr[8..12]tr[13..15]是空叶子值设为单位元求和问题设0最值问题设无穷大或负无穷大。整棵树的下标范围是1到15根节点是1。注意N的取值必须是2的幂且Nn。如果n本身就是2的幂N可以取n但为了统一处理通常取N为大于等于n的最小2的幂。多出来的叶子节点用单位元填充不影响结果。2.2 自底向上的操作逻辑传统线段树是自顶向下递归zkw线段树反过来从叶子节点出发自底向上更新。单点修改时先定位到叶子节点修改值然后不断除以2向上更新父节点直到根节点。区间查询时用两个指针l和r分别从区间左右端点对应的叶子出发向中间靠拢沿途把需要的节点值合并起来。这种自底向上的方式省去了递归的函数调用开销而且循环次数固定就是树的高度也就是log2(N)。对于n1e5的数据树高大约17每次操作循环17次左右非常快。2.3 与递归线段树的对比对比项递归线段树zkw线段树代码长度较长需要写递归函数短循环实现常数大函数调用开销小位运算为主建树方式递归建树直接赋值后自底向上更新区间修改递归懒标记标记永久化或自底向上下传适用场景通用卡常场景、竞赛从表中可以看出zkw线段树的优势主要在常数和代码简洁度上。但它的区间修改写法比递归版本稍微绕一点需要理解标记永久化的思想。下面我会详细讲。3. 单点修改与区间查询最基础的zkw写法3.1 建树从叶子到根建树的步骤很简单先把原数组的值填到叶子节点然后从N-1开始倒着循环到1每个节点tr[i] tr[i1] tr[i1|1]以求和为例。代码如下const int MAXN 100005; int n, N; int tr[MAXN 2]; void build() { // N为大于等于n的最小2的幂 N 1; while (N n) N 1; // 叶子节点赋值 for (int i 1; i n; i) tr[N i - 1] a[i]; // 多余叶子设为单位元 for (int i N n; i 2 * N; i) tr[i] 0; // 自底向上建树 for (int i N - 1; i 1; i--) tr[i] tr[i 1] tr[i 1 | 1]; }这段代码里N的计算用了while循环也可以直接用位运算N 1 (int)ceil(log2(n))但while循环更直观。建树的时间复杂度是O(N)比递归建树的O(n)略大但N最多是2n所以也是O(n)级别。实操心得如果n比较小比如n1N1此时叶子节点就是根节点建树循环不会执行直接tr[1]a[1]即可。这种情况要单独处理否则会出错。3.2 单点修改向上更新单点修改的步骤找到叶子节点下标p N i - 1修改tr[p]然后p 1不断向上更新父节点直到p0。代码如下void update(int i, int val) { int p N i - 1; tr[p] val; p 1; while (p) { tr[p] tr[p 1] tr[p 1 | 1]; p 1; } }这里要注意如果修改的是增量而不是直接赋值可以写成tr[p] delta然后向上更新时也是 delta。但如果是赋值修改就必须重新计算父节点的值不能简单累加。3.3 区间查询双指针向中间靠拢区间查询是zkw线段树的精髓。假设要查询区间[l, r]的和先把l和r转换成叶子节点下标l N l - 1r N r - 1。然后当l r时循环如果l是奇数说明l是右孩子它对应的父节点覆盖的区间不完全在查询范围内所以要把tr[l]加入答案然后l如果r是偶数说明r是左孩子同理把tr[r]加入答案然后r--。最后l 1r 1继续循环。代码如下int query(int l, int r) { int res 0; l N l - 1; r N r - 1; while (l r) { if (l 1) res tr[l]; if (!(r 1)) res tr[r--]; l 1; r 1; } return res; }这个写法的正确性可以通过画图验证。核心思想是l和r分别从两端向中间移动遇到“突出”的节点就把它合并进来然后上升到父节点继续。最终所有被查询区间完全覆盖的节点都会被合并且不会重复。注意查询区间是闭区间[l, r]如果题目给的是左闭右开需要把r减1再传入。另外如果lr直接返回单位元。4. 区间修改标记永久化的实战写法4.1 为什么zkw线段树区间修改要用标记永久化递归线段树做区间修改时通常用懒标记给节点打上标记查询时再下传。但zkw线段树是自底向上的没有递归的“回溯”过程下传标记比较麻烦。所以zkw线段树通常采用标记永久化每个节点维护两个值一个是该节点覆盖区间的总和sum另一个是施加在该节点上的标记add。修改时把标记加到对应节点上同时更新sum查询时把沿途所有祖先节点的标记累加起来作为额外贡献。标记永久化的好处是不需要下传操作代码更简单而且常数更小。缺点是查询时要多累加祖先标记但也就是多循环几次影响不大。4.2 区间修改的实现假设我们要给区间[l, r]每个元素加上val同时维护区间和。定义两个数组sum[]和add[]。修改的步骤如下把l和r转换成叶子下标同时记录原始的l和r用于后续更新sum。用双指针向中间靠拢对于每个被完全覆盖的节点padd[p] valsum[p] val * 该节点覆盖的叶子数。修改完成后从原始的l和r叶子出发向上更新所有祖先的sum。这里的关键是如何知道一个节点覆盖了多少个叶子可以用len[p]表示节点p覆盖的叶子数建树时预处理。对于叶子节点len1对于内部节点len[p] len[p1] len[p1|1]。代码如下int sum[MAXN 2], add[MAXN 2], len[MAXN 2]; void build() { N 1; while (N n) N 1; for (int i 1; i n; i) { sum[N i - 1] a[i]; len[N i - 1] 1; } for (int i N n; i 2 * N; i) { sum[i] 0; len[i] 1; } for (int i N - 1; i 1; i--) { sum[i] sum[i 1] sum[i 1 | 1]; len[i] len[i 1] len[i 1 | 1]; } } void update(int l, int r, int val) { int l0 l, r0 r; l N l - 1; r N r - 1; int l1 l, r1 r; while (l r) { if (l 1) { add[l] val; sum[l] val * len[l]; l; } if (!(r 1)) { add[r] val; sum[r] val * len[r]; r--; } l 1; r 1; } // 向上更新祖先的sum l l1 1; while (l) { sum[l] sum[l 1] sum[l 1 | 1] add[l] * len[l]; l 1; } r r1 1; while (r) { sum[r] sum[r 1] sum[r 1 | 1] add[r] * len[r]; r 1; } }注意这里更新祖先时sum[l]的计算公式是左右孩子的sum之和加上自己的add乘以len。因为add[l]是施加在l节点上的标记它会影响l覆盖的所有叶子但不会体现在孩子的sum里所以要在l这一层加上。4.3 区间查询的实现查询区间[l, r]的和时除了合并沿途节点的sum还要把祖先的add累加起来。具体做法是从叶子出发向上走到根把路径上所有节点的add乘以当前节点覆盖的叶子数累加到答案里。代码如下int query(int l, int r) { int res 0; l N l - 1; r N r - 1; int l0 l, r0 r; while (l r) { if (l 1) res sum[l]; if (!(r 1)) res sum[r--]; l 1; r 1; } // 累加祖先的add l l0 1; while (l) { res add[l] * (min(r0, (l 1 | 1) * len[l 1 | 1] ...)); // 这里需要计算交集长度 l 1; } // 类似处理r0 return res; }上面这段伪代码里计算交集长度比较麻烦。更简单的做法是在查询时对于每个被合并的节点直接把它到根的路径上所有add累加。但这样会重复计算。实际常用的写法是在双指针循环中每次合并节点时同时把该节点的add贡献加上但这样会漏掉祖先的add。我实测下来比较稳妥的写法是查询时先按普通方式合并sum然后单独写一个函数计算某个叶子到根的路径上所有add的贡献。但这样复杂度会变成O(log^2 n)。对于大多数题目O(log^2 n)也能接受但如果要严格O(log n)需要用更精细的写法。实操心得如果题目只要求区间修改单点查询那zkw线段树非常简单只需要在查询时把叶子到根的add累加即可。但如果是区间修改区间查询建议直接用递归线段树或者用zkw的标记永久化但接受O(log^2 n)的查询。我试过几种优化最后发现对于1e5的数据O(log^2 n)和O(log n)的差距在常数上并不明显除非是1e6级别的数据。5. 扩展技巧让zkw线段树适应更多场景5.1 区间最值问题zkw线段树做区间最值时建树和单点修改与求和类似只是把加法换成max或min。区间查询时双指针合并的是最值而不是和。注意单位元的选取求最大值时多余叶子设为负无穷求最小值时设为正无穷。int query_max(int l, int r) { int res -INF; l N l - 1; r N r - 1; while (l r) { if (l 1) res max(res, tr[l]); if (!(r 1)) res max(res, tr[r--]); l 1; r 1; } return res; }区间最值不需要标记永久化因为最值操作不满足区间可减性但也不需要下传标记直接合并即可。5.2 动态开点如果n非常大比如1e9但操作次数只有1e5可以用动态开点。zkw线段树的动态开点比较麻烦因为需要预先知道N。一种折中方案是把操作离线离散化所有出现过的下标然后用zkw线段树维护离散化后的区间。这样N就是离散化后的点数不会太大。5.3 多标记处理如果需要同时支持区间加和区间乘可以用两个标记add和mul。标记永久化时每个节点的sum sum * mul add * len。修改时先乘后加。查询时把路径上的mul和add按顺序累加。这个写法比递归线段树稍微复杂但原理是一样的。6. 常见问题与排查技巧实录6.1 建树时N的取值错误最常见的问题是N取小了导致叶子节点不够。比如n5如果N取4那叶子节点只有4个不够用。必须取Nn的最小2的幂。可以用while循环计算也可以用位运算N 1; while (N n) N 1;6.2 查询时l和r的边界处理查询区间是闭区间[l, r]如果lr直接返回单位元。另外如果l和r超出[1, n]的范围需要先截断。比如查询[0, n1]实际有效范围是[1, n]。6.3 标记永久化的add重复累加在区间修改区间查询时如果查询时累加祖先add的方式不对会导致重复计算。我踩过的坑是在双指针循环中合并节点时把该节点的add也加进去了然后又在祖先累加时加了一次。正确的做法是双指针循环只合并sum祖先add单独累加且每个祖先只累加一次。6.4 常见问题速查表问题现象可能原因解决方法查询结果偏小多余叶子未设单位元建树时把Nn到2N-1的叶子设为单位元修改后查询结果不变未向上更新祖先修改后从叶子向上更新到根区间修改后查询错误标记永久化累加方式错误检查add累加是否重复数组越界N取小了确保Nn且为2的幂单点修改后区间查询错误未更新父节点修改后循环向上更新最后分享一个小技巧如果实在搞不定zkw的区间修改区间查询可以先用递归线段树写然后用zkw只做单点修改区间查询。很多题目其实只需要单点修改这时候zkw的优势非常明显代码短、跑得快性价比极高。我个人的经验是先把单点修改区间查询练熟再逐步过渡到区间修改不要一上来就啃最难的。
