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

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

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

输入格式

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

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

11
8
20

说明/提示

对于 15% 的数据：n ≤ 8，m ≤ 10。
对于 35% 的数据：n ≤ 10³，m ≤ 10⁴。
对于 100% 的数据：1 ≤ n, m ≤ 10⁵，a_i, k 为正数，且任意时刻数列的和不超过 2 × 10¹⁸。

【样例解释】

题解

原理剖析

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

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

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

[!NOTE]

你可以把类声明上面加一行

template<typename T>

并且把类里面的 uint64_t 换成 T、把new SegmentTreeNode后面加上<T> 就可以实现泛型了~

你可以这么实例化它：

SegmentTreeNode<int> intTree(vec);

[!WARNING]

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

代码实现

面向对象的懒加载线段树模版.cpp

/*
万能头、标准命名空间，没啥好讲的，无非方便点。
想节省点二进制大小可以只用 iostream, vector, cstdint。
std命名空间也可以通过在函数/类之类的前面加 std:: 访问。
*/
#include <bits/stdc++.h>
using namespace std;

template<typename T>
class SegmentTreeNode
{
    vector<T>* vec; // 原数组
    T _sum = 0; // 当前区间和
    T pending_change = 0; // 未应用更改（仅当更改区间完全包含当前区间，且未查询到下层区间时）
    int left_bound, right_bound, length, mid; // 左边界，右边界，区间长度，区间中点
    SegmentTreeNode *left_child = NULL, *right_child = NULL; // 左子树，右子树（懒加载）
    bool initialized = false; // 是否已读取过数据
    
    // 初始化器
    void initializer(vector<T>& v, int lb, int rb){
        if(lb > rb || lb < 0 || rb > (int)(v.size())-1) throw invalid_argument("Invalid bounds.");
        vec = &v;
        left_bound = lb;
        right_bound = rb;
        length = rb - lb;
        mid = lb + length / 2;
    }
    
public:
    // 带边界的初始化
    SegmentTreeNode(vector<T>& v, int lb, int rb) { initializer(v, lb, rb); }
    // 用数组直接初始化
    SegmentTreeNode(vector<T>& v) { initializer(v, 0, (int)(v.size())-1); }
    // 递归析构函数
    ~SegmentTreeNode()
    {
        if (left_child != NULL) delete left_child;
        if (right_child != NULL) delete right_child;
    }
    // 范围修改
    void range_add(const int lb, const int rb, const T n)
    {
        // 边界检查
        if (lb > rb || lb < left_bound || rb > right_bound) throw invalid_argument("invalid bounds!");
        // 若全匹配，标记懒加载，直接退出
        if (lb == left_bound && rb == right_bound) return add_pending(n);
        // 否则更新区间和
        _sum += n * (rb - lb + 1);
        // 递归更新子区间
        const bool at_left = lb <= mid, at_right = rb > mid;
        if (at_left) left()->range_add(lb, min(rb, mid), n);
        if (at_right) right()->range_add(max(lb, mid + 1), rb, n);
    }
    // 范围查询
    uint64_t range_sum(const int lb, const int rb)
    {
        // 边界检查
        if (lb > rb || lb < left_bound || rb > right_bound) throw invalid_argument("invalid bounds!");
        // 若全匹配，返回当前区间和
        if (lb == left_bound && rb == right_bound) return sum();
        // 是否在左子树，是否在右子树
        const bool at_left = lb <= mid, at_right = rb > mid;
        // 若存在懒加载更新，向下推送，确保准确度
        if (pending_change)
        {
            left()->add_pending(pending_change);
            right()->add_pending(pending_change);
            _sum += pending_change * (length + 1);
            pending_change = 0;
        }
        // 递归查询子树
        T rs = 0;
        if (at_left) rs += left()->range_sum(lb, min(rb, mid));
        if (at_right) rs += right()->range_sum(max(lb, mid + 1), rb);
        return rs;
    }
    // 获取当前区间和
    uint64_t sum()
    {
        if (!initialized) // 如未加载
        {
            if (length) _sum = left()->sum() + right()->sum(); // 若是区间，递归查询子树
            else _sum = (*vec)[left_bound]; // 如是叶子，直接获取原数组
            initialized = true; // 标记已加载
        }
        return _sum + pending_change * (length + 1); // 实际值+懒加载*长度=区间和
    }
    // 获取左子树，若未初始化则创建
    SegmentTreeNode* left()
    {
        if (!length) throw invalid_argument("cannot create subtree because the node is leaf.");
        if (left_child == NULL) left_child = new SegmentTreeNode(*vec, left_bound, mid);
        return left_child;
    }
    // 获取右子树，如未初始化则创建
    SegmentTreeNode* right()
    {
        if (!length) throw invalid_argument("cannot create subtree because the node is leaf.");
        if (right_child == NULL) right_child = new SegmentTreeNode(*vec, mid + 1, right_bound);
        return right_child;
    }
    // 标记懒加载
    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);
    */
    vector<uint64_t> a;
    uint64_t n, m;
    cin >> n >> m;
    a.reserve(n);
    while(n--){
        uint64_t x;
        cin >> x;
        a.emplace_back(x);
    }
    
    SegmentTreeNode<uint64_t> tree(a);
    
    while(m--){
        uint64_t t, x, y, k;
        cin >> t;
        switch(t){
        case 1:
            cin >> x >> y >> k;
            tree.range_add(x-1, y-1, k);
            break;
        case 2:
            cin >> x >> y;
            cout << tree.range_sum(x-1, y-1) << endl;
            break;
        }
    }
    
    return 0;
}

[!NOTE]

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