zkw 线段树-原理及其扩展
媒介许多算法的本质是统计。线段树用于统计，是沟通原数组与前缀和的桥梁。
《统计的力量》清华大学-张昆玮
关于线段树
前置知识：线段树 OIWiki。
线段树是一种专门维护区间问题的数据布局。
线段树对信息进行二进制化处置惩罚并在树形布局上维护，以此让处置惩罚速度达到 \(O(\log{n})\) 级别。
线段树的实现方式
由于线段树的树形布局特点，每次修改查询可以从根节点向下二分查找必要用到的节点，因此较为普遍且快捷的线段树会利用递归实现。
但递归实现的线段树由于每次要从根节点递归向下传递子树信息，导致常数较大，轻易被卡常，所以出现了常数更小的递推实现的线段树（敬拜 zkw 大佬）。
zkw 线段树
先来讲一些小原理。
一、原理
由于递归实现的线段树不是一棵满二叉树，其叶子节点位置不确定，导致每次操纵都必要从根节点开始自上而下递归依次探求叶子节点，回溯时进行维护，递归过程常数就比较大了。
所以 zkw 线段树就直接建出一棵满二叉树，原序列信息都维护在最底层。严酷规定父子节点关系，同层节点的子树大小相等。
如许每个叶子节点都可以直接找到并修改，由于二叉树父子节点的二进制关系，就可以递推直接找到对应节点的父亲节点自下而上地维护节点关系。
二、初始化
1、建树
对长度为 \(n\) 的序列建一棵 zkw 线段树，其至少有 \(n+2\) 个叶子节点。其中有 2 个用来帮助维护区间信息的虚点，有 \(n\) 个用来存原序列信息的节点。
如图（【模板】线段树 1的样例为例，下同）：
https://cdn.luogu.com.cn/upload/image_hosting/fjaow3vw.png
建树时先求出虚点 \(P\) 位置，然后直接向其他叶子节点读入信息即可:
//先求虚点 PP = 1;while(P
页:
[1]