注意：本文不会专门探讨zkw线段树，关于该数据结构见这篇文章。

        zkw线段树是不基于递归的线段树，效率在树状数组和递归线段树之间。下面给出可以AC洛谷模板题的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<cstdio>

#define N 100005
using namespace std;
long long tree[N << 2] = {0}, add[N << 2] = {0};
int n, m, bit;

inline long long read() {
    char e = getchar();
    long long s = 0, k = 0;
    while ((e < '0' || e > '9') && e != '-')e = getchar();
    if (e == '-')k = 1, e = getchar();
    while (e >= '0' && e <= '9')s = s * 10 + e - '0', e = getchar();
    return k ? -s : s;
}

inline void build(int x) {
    for (bit = 1; bit <= x + 1; bit <<= 1);
    for (int i = bit + 1; i <= bit + x; i++)tree[i] = read();
    for (int i = bit - 1; i; i--)tree[i] = tree[i << 1] + tree[i << 1 | 1];
}

inline void modify(int x, long long k) {
    for (int i = bit + x; i; i >>= 1)tree[i] += k;
}

inline void modify(int l, int r, long long k) {
    if (l == r) {
        modify(l, k);
        return;
    }
    int lNum = 0, rNum = 0, num = 1, s, t;
    for (s = bit + l - 1, t = bit + r + 1; s ^ t ^ 1; s >>= 1, t >>= 1, num <<= 1) {
        tree[s] += k * lNum, tree[t] += k * rNum;
        if (~s & 1)add[s ^ 1] += k, tree[s ^ 1] += k * num, lNum += num;
        if (t & 1)add[t ^ 1] += k, tree[t ^ 1] += k * num, rNum += num;
    }
    for (; s; s >>= 1, t >>= 1)tree[s] += lNum * k, tree[t] += rNum * k;
}

inline long long query(int l, int r) {
    long long ans = 0;
    int lNum = 0, rNum = 0, num = 1, s, t;
    for (s = bit + l - 1, t = bit + r + 1; s ^ t ^ 1; s >>= 1, t >>= 1, num <<= 1) {
        if (add[s])ans += add[s] * lNum;
        if (add[t])ans += add[t] * rNum;
        if (~s & 1)ans += tree[s ^ 1], lNum += num;
        if (t & 1)ans += tree[t ^ 1], rNum += num;
    }
    for (; s; s >>= 1, t >>= 1)ans += add[s] * lNum, ans += add[t] * rNum;
    return ans;
}


int main() {
    n = read(), m = read();
    build(n);
    for (int i = 1; i <= m; i++) {
        long long a, b, c;
        if (read() == 1)a = read(), b = read(), c = read(), modify(a, b, c);
        else a = read(), b = read(), cout << query(a, b) << endl;
    }
    return 0;
}