【模板】线段树 1

题意

维护数列，支持区间加法和区间求和。

思路

懒标记线段树

节点保存覆盖区间的和。整段加 value 时，区间和增加 length * value，并把 value 记在懒标记中；只有在需要访问孩子时才下传。区间查询和修改都只访问对数个节点。

双树状数组

设差分数组 d[i] = a[i] - a[i-1]。区间 [l,r] 加 value 只改变 d[l] 和 d[r+1]。

一棵 Fenwick 维护 d[i]，另一棵维护 i*d[i]。原数组前缀和满足：

\begin{aligned} prefix(x) &=\sum_{i=1}^{x}a_i \\ &=(x+1)\sum_{i=1}^{x}d_i-\sum_{i=1}^{x}i\cdot d_i \end{aligned}

因此区间和仍为 prefix(r) - prefix(l-1)。这个做法只适用于本题的区间加与区间和；如果还要处理区间赋值或乘法，应使用线段树。

Python 知识

sys.stdin.buffer.readline 减少大量操作的输入开销。
用几个同长度列表保存线段树字段，比为每个节点创建对象更省内存。
if query_left <= middle 和 if middle < query_right 只递归到真正相交的子树。

代码

懒标记线段树

python

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
66
67
68
69import sys


sys.setrecursionlimit(1_000_000)
input = sys.stdin.buffer.readline
n, operations = map(int, input().split())
values = list(map(int, input().split()))
tree = [0] * (4 * n)
lazy = [0] * (4 * n)


def build(node, left, right):
    if left == right:
        tree[node] = values[left - 1]
        return
    middle = (left + right) // 2
    build(node * 2, left, middle)
    build(node * 2 + 1, middle + 1, right)
    tree[node] = tree[node * 2] + tree[node * 2 + 1]


def apply(node, length, value):
    tree[node] += length * value
    lazy[node] += value


def push(node, left, right):
    if lazy[node] and left != right:
        middle = (left + right) // 2
        apply(node * 2, middle - left + 1, lazy[node])
        apply(node * 2 + 1, right - middle, lazy[node])
        lazy[node] = 0


def update(node, left, right, query_left, query_right, value):
    if query_left <= left and right <= query_right:
        apply(node, right - left + 1, value)
        return
    push(node, left, right)
    middle = (left + right) // 2
    if query_left <= middle:
        update(node * 2, left, middle, query_left, query_right, value)
    if middle < query_right:
        update(node * 2 + 1, middle + 1, right, query_left, query_right, value)
    tree[node] = tree[node * 2] + tree[node * 2 + 1]


def query(node, left, right, query_left, query_right):
    if query_left <= left and right <= query_right:
        return tree[node]
    push(node, left, right)
    middle = (left + right) // 2
    answer = 0
    if query_left <= middle:
        answer += query(node * 2, left, middle, query_left, query_right)
    if middle < query_right:
        answer += query(node * 2 + 1, middle + 1, right, query_left, query_right)
    return answer


build(1, 1, n)
answers = []
for _ in range(operations):
    operation = list(map(int, input().split()))
    if operation[0] == 1:
        update(1, 1, n, operation[1], operation[2], operation[3])
    else:
        answers.append(str(query(1, 1, n, operation[1], operation[2])))
print("\n".join(answers))

原有 C++ 模板仍保留：

cpp

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, m;
long long a[MAXN];
long long tree_sum[MAXN * 4]; // tree_sum[p] 表示当前线段树节点覆盖区间的和。
long long lazy_add[MAXN * 4]; // lazy_add[p] 表示还没有下传给孩子的区间加标记。

void build(int p, int l, int r) {
    if (l == r) {
        tree_sum[p] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    tree_sum[p] = tree_sum[p * 2] + tree_sum[p * 2 + 1];
}

void apply_add(int p, int l, int r, long long value) {
    tree_sum[p] += value * (r - l + 1);
    lazy_add[p] += value;
}

void push_down(int p, int l, int r) {
    if (lazy_add[p] == 0 || l == r) {
        return;
    }
    int mid = (l + r) / 2;
    apply_add(p * 2, l, mid, lazy_add[p]);
    apply_add(p * 2 + 1, mid + 1, r, lazy_add[p]);
    lazy_add[p] = 0;
}

void range_add(int p, int l, int r, int ql, int qr, long long value) {
    if (ql <= l && r <= qr) {
        apply_add(p, l, r, value);
        return;
    }
    push_down(p, l, r);
    int mid = (l + r) / 2;
    if (ql <= mid) {
        range_add(p * 2, l, mid, ql, qr, value);
    }
    if (qr > mid) {
        range_add(p * 2 + 1, mid + 1, r, ql, qr, value);
    }
    tree_sum[p] = tree_sum[p * 2] + tree_sum[p * 2 + 1];
}

long long query_sum(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return tree_sum[p];
    }
    push_down(p, l, r);
    int mid = (l + r) / 2;
    long long answer = 0;
    if (ql <= mid) {
        answer += query_sum(p * 2, l, mid, ql, qr);
    }
    if (qr > mid) {
        answer += query_sum(p * 2 + 1, mid + 1, r, ql, qr);
    }
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, 1, n);

    for (int i = 1; i <= m; i++) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) {
            long long k;
            cin >> k;
            range_add(1, 1, n, x, y, k);
        } else {
            cout << query_sum(1, 1, n, x, y) << '\n';
        }
    }

    return 0;
}

双树状数组

cpp

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
66
67
68
69
70
71
72
73
74
75
76#include <bits/stdc++.h>
using namespace std;

struct RangeFenwick {
    int n = 0;
    vector<long long> bit_diff, bit_weighted;

    RangeFenwick(int n = 0) { init(n); }

    void init(int size) {
        n = size;
        bit_diff.assign(n + 1, 0);
        bit_weighted.assign(n + 1, 0);
    }

    static int lowbit(int x) { return x & -x; }

    void add(vector<long long> &bit, int pos, long long value) {
        for (int i = pos; i <= n; i += lowbit(i)) {
            bit[i] += value;
        }
    }

    long long sum(const vector<long long> &bit, int pos) const {
        long long answer = 0;
        for (int i = pos; i > 0; i -= lowbit(i)) {
            answer += bit[i];
        }
        return answer;
    }

    void range_add(int left, int right, long long value) {
        add(bit_diff, left, value);
        add(bit_diff, right + 1, -value);
        add(bit_weighted, left, value * left);
        add(bit_weighted, right + 1, -value * (right + 1));
    }

    long long prefix_sum(int pos) const {
        return 1LL * (pos + 1) * sum(bit_diff, pos)
             - sum(bit_weighted, pos);
    }

    long long range_sum(int left, int right) const {
        return prefix_sum(right) - prefix_sum(left - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    RangeFenwick bit(n);
    for (int i = 1; i <= n; ++i) {
        long long value;
        cin >> value;
        bit.range_add(i, i, value);
    }

    while (m--) {
        int operation, left, right;
        cin >> operation >> left >> right;
        if (operation == 1) {
            long long value;
            cin >> value;
            bit.range_add(left, right, value);
        } else {
            cout << bit.range_sum(left, right) << '\n';
        }
    }

    return 0;
}

复杂度

懒标记线段树：建树 O(n)，每次操作 O(log n)，空间 O(n)。
双树状数组：当前实现逐点初始化为 O(n log n)，每次操作 O(log n)，空间 O(n)。

总结

懒标记线段树把整段修改记在区间节点上；双树状数组则把区间加拆成差分边界，并用两个差分前缀量还原区间和。两种方法都能完成本题，但维护的信息不同。

【模板】线段树 1

目录

题意

思路

懒标记线段树

双树状数组

Python 知识

代码

懒标记线段树

双树状数组

复杂度

总结