[C++] P3372 【模板】线段树 1

发表于 更新于 分类于

如题，已知一个数列 {ai}，你需要进行下面两种操作：

  1. 将某区间每一个数加上 k。
  2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 n, m，分别表示该数列数字的个数和操作的总个数。

第二行包含 n 个用空格分隔的整数 ai，其中第 i 个数字表示数列第 i 项的初始值。

接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下：

  1. 1 x y k：将区间 [x, y] 内每个数加上 k。
  2. 2 x y：输出区间 [x, y] 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

输出 #1

1
2
3
11
8
20

说明/提示

对于 15% 的数据：n ≤ 8，m ≤ 10。
对于 35% 的数据：n ≤ 103，m ≤ 104。
对于 100% 的数据：1 ≤ n, m ≤ 105，ai, k 为正数，且任意时刻数列的和不超过 2 × 1018。

【样例解释】

题解

原理剖析

二分线段树，树如其名，通过把一个长为 n 的数组映射到一段对应长线段上，在这个线段上建立二叉树，其中每个单位长度对应数组的一个元素和二叉树的一个叶子结点，由此实现区间操作。不难发现理想情况下更改复杂度和查询复杂度均为 O(log n) 。

想要捣鼓出一个线段树并不难，但是想要控制单次操作涉及的节点数量较为困难，这里推荐使用 C++ 的面向对象特性~（虽然你用struct也是一样的就是）

如下是我实现的一个二叉线段树泛型类（存储的是区间和，操作是区间加）~

[!WARNING]

由于原数组是只读引用，因此你不应该在原数组上做任何操作，读取也是不准确的。

代码实现

面向对象的懒加载线段树模版.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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <cassert>
#include <type_traits>
#include <span>
#include <stdexcept>
#include <memory>
#include <vector>
#include <iostream>

template<typename T>
class SegmentTreeNode
{
    static_assert(std::is_arithmetic_v<T>, "SegmentTreeNode requires an arithmetic type"); // 确保 T 是算数类型
    
    const std::span<T> vec; // 原始数组
    T _sum = 0; // 区间和
    T pending_change = 0; // 未应用更改（仅当更改区间完全包含当前区间，且未查询到下层区间时）
    const size_t left, right, length, mid; // 左边界，右边界，长度，中点
    std::unique_ptr<SegmentTreeNode> left_child_ptr{}, right_child_ptr{}; // 左子树，右子树（懒加载）
    bool initialized = false; // 是否已读取过数据
    
public:
    // 构建函数
    SegmentTreeNode(const std::span<T> v, const size_t l, const size_t r)
        : vec(v), left(l), right(r), length(r-l), mid(l+(r-l)/2)
    {
        if(l>r || !v.size() || r>v.size()-1) throw std::invalid_argument("Invalid SegmentTreeNode::SegmentTreeNode argument");
    }
    
    explicit SegmentTreeNode(const std::span<T> v) : SegmentTreeNode(v, 0, v.size()-1) {}
    
    // 范围修改
    void range_add(const size_t lb, const size_t rb, const T n)
    {
        // 边界检查
        if (lb > rb || lb < left || rb > right) throw std::invalid_argument("Invalid SegmentTreeNode::range_add argument");
        // 若全匹配，标记懒加载，直接退出
        if (lb == left && rb == right) return add_pending(n);
        // 否则更新区间和
        _sum += n * (rb - lb + 1);
        // 递归更新子区间
        if (lb <= mid) left_child()->range_add(lb, std::min(rb, mid), n);
        if (rb > mid) right_child()->range_add(std::max(lb, mid + 1), rb, n);
    }
    // 范围查询
    T range_sum(const size_t lb, const size_t rb)
    {
        // 边界检查
        if (lb > rb || lb < left || rb > right) throw std::invalid_argument("Invalid SegmentTreeNode::range_sum argument");
        // 若全匹配，返回当前区间和
        if (lb == left && rb == right) return sum();
        // 若存在懒加载更新，向下推送，确保准确度
        if (pending_change)
        {
            left_child()->add_pending(pending_change);
            right_child()->add_pending(pending_change);
            _sum += pending_change * (length + 1);
            pending_change = 0;
        }
        // 递归查询子树
        T rs = 0;
        if (lb <= mid) rs += left_child()->range_sum(lb, std::min(rb, mid));
        if (rb > mid) rs += right_child()->range_sum(std::max(lb, mid + 1), rb);
        return rs;
    }
    // 获取当前区间和
    T sum()
    {
        if (!initialized) // 如未加载
        {
            if (length) _sum = left_child()->sum() + right_child()->sum(); // 若是区间，递归查询子树
            else _sum = vec[left]; // 如是叶子，直接获取原数组
            initialized = true; // 标记已加载
        }
        return _sum + pending_change * (length + 1); // 实际值+懒加载*长度=区间和
    }
    // 获取左子树，若未初始化则创建
    SegmentTreeNode* left_child()
    {
        if (!length) throw std::invalid_argument("cannot create subtree because the node is leaf.");
        if (!left_child_ptr) left_child_ptr = std::make_unique<SegmentTreeNode>(vec, left, mid);
        return left_child_ptr.get();
    }
    // 获取右子树，如未初始化则创建
    SegmentTreeNode* right_child()
    {
        if (!length) throw std::invalid_argument("cannot create subtree because the node is leaf.");
        if (!right_child_ptr) right_child_ptr = std::make_unique<SegmentTreeNode>(vec, mid + 1, right);
        return right_child_ptr.get();
    }
    // 标记懒加载
    void add_pending(const uint64_t n)
    {
        pending_change += n;
    }
};

int main()
{
    /*
    // 真拼这点？
    freopen("p3372.in", "r", stdin);
    freopen("p3372.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    */
    std::vector<uint64_t> a;
    uint64_t n, m;
    std::cin >> n >> m;
    a.reserve(n);
    while(n--){
        uint64_t x;
        std::cin >> x;
        a.emplace_back(x);
    }
    
    SegmentTreeNode<uint64_t> tree(a);
    
    while(m--){
        uint64_t t, x, y, k;
        std::cin >> t;
        switch(t){
        case 1:
            std::cin >> x >> y >> k;
            tree.range_add(x-1, y-1, k);
            break;
        case 2:
            std::cin >> x >> y;
            std::cout << tree.range_sum(x-1, y-1) << std::endl;
            break;
        }
    }
    
    return 0;
}

[!NOTE]

这个实现很多地方不符合现代C++标准……但是给AI的话他就直接把懒加载给我弄没了！真抽象了也就是……