洛谷-P3374 [模板]树状数组1（单点修改，区间查询）

题目描述

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

• 将某一个数加上 xx
• 求出某区间每一个数的和

输入格式

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

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

接下来 mm 行每行包含 33 个整数，表示一个操作，具体如下：

• 1 x k 含义：将第 xx 个数加上 kk
• 2 x y 含义：输出区间 [x,y][x,y] 内每个数的和

输出格式

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

输入输出样例

输入

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

输出

14
16

说明/提示

【数据范围】

对于30%的数据，$1 \leq n \leq 8, 1 \leq m \leq 10$;

对于70%的数据，$1 \leq n, m \leq 10^4$;

对于100%的数据，$1\leq n, m \leq 5 \times 10^5$。

---

虽然这个模板是给树状数组的，其实也可以用**线段树**的方法来求解：

#include <iostream>
#include <vector>

using namespace std;

const int INF = 0x0ffffff;
int n = 1000001;

struct Node {
    int left, right;
    long long sum;

    //Node() : left(0), right(0), maxNum(0), minNum(0) {}
};

vector<Node> v(n << 2);
vector<int> num(n);

inline void update(int k)
{
    v[k].sum = v[k << 1].sum + v[k << 1 | 1].sum;
}

void build(int k, int leftPos, int rightPos)
{
    v[k].left = leftPos;
    v[k].right = rightPos;

    if (leftPos == rightPos) {
        v[k].sum = num[leftPos];
        return;
    }

    int mid = v[k].left + ((v[k].right - v[k].left) >> 1);
    build(k << 1, leftPos, mid);
    build(k << 1 | 1, mid + 1, rightPos);
    update(k);
}

void change(int k, int target, int value) 
{
    if (v[k].left == v[k].right) {
        v[k].sum += value;
        return;
    }

    int mid = v[k].left + ((v[k].right - v[k].left) >> 1);
    if (target <= mid) change(k << 1, target, value);
    else change(k << 1 | 1, target, value);
    update(k);
}

int query(int k, int leftPos, int rightPos)
{
    if (v[k].left == leftPos && v[k].right == rightPos) {
        return v[k].sum;
    }

    int mid = v[k].left + ((v[k].right - v[k].left) >> 1);
    if (rightPos <= mid) return query(k << 1, leftPos, rightPos);
    else if (leftPos > mid) return query(k << 1 | 1, leftPos, rightPos);

    return query(k << 1, leftPos, mid) + query(k << 1 | 1, mid + 1, rightPos);
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int Q;
    cin >> n >> Q;
    for (int i = 1; i <= n; ++i) {
        cin >> num[i];
    }

    build(1, 1, n);

    while (Q--) {
        int action;
        cin >> action;
        if (action & 1) { //action == 1
            int target, value;
            cin >> target >> value;
            change(1, target, value);
        }
        else {
            int leftPos, rightPos;
            cin >> leftPos >> rightPos;
            cout << query(1, leftPos, rightPos) << endl;
        }
    }

    return 0;
}