洛谷 P3374 【模板】树状数组 1

// P3374 第 ① 版：**题目怎么说就怎么做** —— 改是 O(1)，查是 O(区间长度)
//
// ★ 它值多少分，题面自己写着（读数据范围的时候顺手把它乘出来）：
//     · 「对于 30% 的数据，1 ≤ n ≤ 8，1 ≤ m ≤ 10」  ⇒ 80 次加法，★ 稳拿 30 分；
//     · 「对于 70% 的数据，1 ≤ n, m ≤ 10⁴」        ⇒ 10⁸ 次，本机约 0.05 秒 ⇒ ★ 也过得去；
//     · 顶格 n = m = 5×10⁵                        ⇒ **2.5×10¹¹ 次**，一秒的时限差着四个数量级。
//
// ⇒ 所以这一版不是「白写的」：它是 70 分，而且它是后面所有版本的**参照物**（对拍拿它当标准答案）。

#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<long long> a(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    string out;
    for (int q = 0; q < m; q++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x; long long k;
            cin >> x >> k;
            a[x] += k;                       // ★ 改：O(1)
        } else {
            int x, y;
            cin >> x >> y;
            long long s = 0;
            for (int i = x; i <= y; i++) s += a[i];   // ⚠ 查：一个一个加，O(y − x + 1)
            out += to_string(s);
            out += '\n';
        }
    }
    cout << out;
    return 0;
}

// P3374【模板】树状数组 1 —— ★ 这一版就能 AC（单点加 + 区间和）
//
// 和本章正文那道题（fast.cpp）**几乎是同一份代码**，差别只有两处：
//   ① 正文那道题末尾多问一句「整个数组的和」，这道题没有；
//   ② ★★ 题面的那句保证不一样 —— 而那句话正好是本页最值钱的东西（见下）。
//
// ============ ★★★ 题面替你把「要不要 long long」这笔账付了 ============
//
//   题面最后一行：**「数据保证对于任意时刻，a 的任意子区间（包括长度为 1 和 n
//   的子区间）和均在 [−2³¹, 2³¹) 范围内。」**
//
//   ⇒ 那个区间**逐字就是 int 的范围**（−2 147 483 648 … 2 147 483 647）。
//   ⇒ 而它保证的不只是「答案」：
//        · c[i] = a[i−lowbit(i)+1] + … + a[i]  —— **本身就是一个子区间和** ⇒ 在范围内；
//        · sum(r) 一路累加，每一步的部分和是 (j, r] 这一段的和 —— **也是子区间和** ⇒ 在范围内；
//        · 答案 sum(r) − sum(l−1) = [l, r] 的和 —— 还是子区间和。
//     ⇒ **整棵树、每一个中间值，全在 int 里。**（p3374Count.cpp 在两个档上量过最大绝对值。）
//
//   ⚠ 但这里仍然写 long long：**因为那句保证一旦被拿掉，int 立刻就错**
//     （生成器档 2 专门造违反它的数据，int 版 300 / 300 全错）——
//     ⇒ 这一页的结论不是「用 int」，是**「这道题能用 int，而这是题面给的，不是算法给的」**。
//
// 复杂度 O((n + m) log n)：顶格 n = m = 5×10⁵ ⇒ 约 2×10⁷ 次基本操作。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 500005;
long long c[MAXN];
int n, m;

inline int lowbit(int i) { return i & -i; }

void add(int p, long long x) {
    for (int i = p; i <= n; i += lowbit(i)) c[i] += x;
}

long long sum(int r) {
    long long s = 0;
    for (int i = r; i > 0; i -= lowbit(i)) s += c[i];
    return s;
}

int main() {
    ios::sync_with_stdio(false);          // ★ 这一句在这道题上值 4.7 倍（245 → 52 毫秒），见第 ⑤ 步
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;

    // ★ O(n) 建树：a[i] 先落进 c[i]，再把 c[i] 整个交给它爸爸 i + lowbit(i)
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        c[i] += x;
        int f = i + lowbit(i);
        if (f <= n) c[f] += c[i];
    }

    string out;
    for (int q = 0; q < m; q++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x; long long k;
            cin >> x >> k;
            add(x, k);
        } else {
            int x, y;
            cin >> x >> y;
            out += to_string(sum(y) - sum(x - 1));   // ⚠ 是 x−1
            out += '\n';
        }
    }
    cout << out;
    return 0;
}