zkw线段树！！！

ZKW线段树！！！

出处 : 统计的力量 by THU张昆玮

跟普通线段树的区别：

1. 非递归调用， 常数小

2. 堆式满二叉树储存，是点树

3. 信息向上传递

大概来一张图来表现普通线段树与zkw重口味线段树的储存方式的差距。

这个是普通的线段树

zkw线段树

qwq有没有dalao安利我绘图工具啊，windows自带画板快把强迫症逼死了啊啊啊啊啊

是不是非常的简单明了==
反正就是能够发现，你可以很快的找到叶子节点的位置
作为二叉树，线段树的标号是这样的

转换成二进制之后是这样的

很显然nd[x]的父亲节点是nd[x >> 1], 而nd[x]的两个儿子节点的标号分别是nd[x << 1]和nd[x << 1 | 1].

接下来是求区间和的各个操作的演示代码

inline void build()

建树十分简单
PS: 为了保证叶子节点都在同一层，必须保证最后一层的节点数量是大于n的最小的2的幂，也就是代码中的M

inline void push_up(int x) { // 上传过程
    nd[x] = nd[x << 1] + nd[x << 1 | 1];
}

inline void build() {
    while(M <= n + 1) { // M可以等于n 所以要M <= n + 1
        M <<= 1;
    }
    for(int i = M + 1; i <= M + n; i++) { // 处理叶子节点
        nd[i] = get_num();
    }
    for(int i = M; i >= 1; i--) { // 处理父节点
        push_up(i);
    }
}

叶子节点所在的层上的节点数为M， 叶子结点之前的节点数也是M，然后更新过程就可以这样的优美

inline void change_one_point(int x, int k)

单点修改的过程也是十分的简单， 只需要找到要修改的值所在的叶子节点，更新之后一路往上传就行, 时间复杂度O(logn)

inline void change_one_point(int x , int k) {
    x += M;
	nd[x] += k;
    for(x >>= 1; x; x >>= 1) {
        push_up(x);
    }
}

inline void change_section(int l, int r, int k)

这是个坑，暂时不解决

inline int query(int l, int r)

inline int query(int l, int r) {
    int ans = 0;
    for(l = M + l - 1, r = M + r + 1; l ^ r ^ 1; l >>= 1, r >>= 1) { // l = M + l - 1, r = M + r + 1, 意思是将l 和 r 变成开区间，l ^ r ^ 1  -->  not l ^ r == 1  -->  l 和 r不是同一节点的两个子节点
        if(~l & 1) ans += nd[l + 1];// l是左子区间                       
        if(r & 1) ans += nd[r - 1]; // r是右子区间                       
    }
    return ans;
}

一大坨毒瘤的位运算。。。
每个位运算的意思都在代码里解释了，如果还是感觉毒瘤可以尝试看看zkw论文里的伪代码

未完待续…