洛谷 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;
}

// P3374 第 ④ 版：**线段树**（[第 39 章](/ch/39-segment-tree/)那把锤子）
//
// ★ 这一节是 2026-09-01 补的：这道题在**第 39 章的题单里又出现了一次**，
//   而那一章的要求是「第 38 章交过的那道，这次用线段树再交一遍」。
//   ⇒ 于是同一道题有了两份正解，可以把它们并排称一称：行数、耗时、以及「改成别的问题要动几处」。
//
// ⚠ 和第 39 章正文里那份 single.cpp 的唯一差别：**这一份不打末尾那一行**。
//   （第 39 章为了教学，在第 38 章那道题上多问了一行「整个数组的和」；**真题不要**。）
//
// ★ 单点改是「区间加」的特例（l = r）⇒ 这道题**用不着懒标记**：
//   一路递归到那个叶子改掉，回溯时 pushup。没有 lz、没有 pushdown、没有「乘区间长度」。
//
// 复杂度：建树 O(n)，每次操作 O(log n) —— 和树状数组同级，差别全在常数和代码量上。

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

const int MAXN = 500005;
long long sm[MAXN * 4];
long long a[MAXN];
int n, m;

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

void add(int o, int l, int r, int p, long long x) {
    if (l == r) { sm[o] += x; return; }
    int mid = (l + r) / 2;
    if (p <= mid) add(o * 2, l, mid, p, x);
    else add(o * 2 + 1, mid + 1, r, p, x);
    sm[o] = sm[o * 2] + sm[o * 2 + 1];
}

long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sm[o];
    int mid = (l + r) / 2;
    long long s = 0;
    if (ql <= mid) s += query(o * 2, l, mid, ql, qr);
    if (qr > mid) s += query(o * 2 + 1, mid + 1, r, ql, qr);
    return s;
}

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

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

    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(1, 1, n, x, k);
        } else {
            int x, y;
            cin >> x >> y;
            out += to_string(query(1, 1, n, x, y));
            out += '\n';
        }
    }
    cout << out;
    return 0;
}

// P3374 补的那一节用的度量程序：./p3374SegCount csv
//
//   ms    : 顶格 n = m = 5×10⁵ 上，**同一批操作**分别喂给树状数组和线段树，
//           在进程内用 steady_clock 量（**不含读入** —— 这道题读入 245 毫秒，
//           不减掉它，两种做法的差别会被整个吃掉，见[第 34 章 P3366](/sol/p3366/) 那条）。
//   steps : 换一把机器无关的尺子 —— 两边各「碰了多少个节点」。
//   same  : 两种做法逐个答案相同。
//
// ⚠ 这里**复刻**了 p3374Gen.cpp 档 4 的逻辑（同一个 mt19937、同一个种子公式）。

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

struct Op { int type, x, y; long long k; };

int n, m;
static long long steps;

/* ---- 树状数组 ---- */
static vector<long long> c;
static inline int lowbit(int x) { return x & -x; }
static void bAdd(int i, long long v) { for (; i <= n; i += lowbit(i)) { c[i] += v; steps++; } }
static long long bSum(int i) { long long s = 0; for (; i > 0; i -= lowbit(i)) { s += c[i]; steps++; } return s; }

/* ---- 线段树 ---- */
static vector<long long> sm;
static void build(int o, int l, int r, const vector<long long>& a) {
    steps++;
    if (l == r) { sm[o] = a[l]; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid, a); build(o * 2 + 1, mid + 1, r, a);
    sm[o] = sm[o * 2] + sm[o * 2 + 1];
}
static void sAdd(int o, int l, int r, int p, long long x) {
    steps++;
    if (l == r) { sm[o] += x; return; }
    int mid = (l + r) / 2;
    if (p <= mid) sAdd(o * 2, l, mid, p, x); else sAdd(o * 2 + 1, mid + 1, r, p, x);
    sm[o] = sm[o * 2] + sm[o * 2 + 1];
}
static long long sQry(int o, int l, int r, int ql, int qr) {
    steps++;
    if (ql <= l && r <= qr) return sm[o];
    int mid = (l + r) / 2;
    long long s = 0;
    if (ql <= mid) s += sQry(o * 2, l, mid, ql, qr);
    if (qr > mid) s += sQry(o * 2 + 1, mid + 1, r, ql, qr);
    return s;
}

int main(int argc, char** argv) {
    bool csv = (argc > 1 && string(argv[1]) == "csv");

    // ⚠ 复刻 p3374Gen.cpp 的档 4
    mt19937 rng(1u * 1000003u + 20260902u);
    n = 500000; m = 500000;
    long long hi = 1000;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) { long long v = (long long)(rng() % (unsigned long long)(2 * hi + 1)) - hi; a[i] = v; }
    vector<Op> ops;
    for (int q = 0; q < m; q++) {
        int x = 1 + (int)(rng() % (unsigned)n);
        int y = 1 + (int)(rng() % (unsigned)n);
        if (x > y) swap(x, y);
        int op = 1 + (int)(rng() % 2u);
        long long k = (long long)(rng() % (unsigned long long)(2 * hi + 1)) - hi;
        ops.push_back({op, x, y, k});
    }

    vector<long long> o1, o2;
    c.assign(n + 2, 0);
    steps = 0;
    auto t0 = steady_clock::now();
    for (int i = 1; i <= n; i++) { c[i] += a[i]; int f = i + lowbit(i); if (f <= n) c[f] += c[i]; steps++; }
    for (const Op& o : ops) {
        if (o.type == 1) bAdd(o.x, o.k);
        else o1.push_back(bSum(o.y) - bSum(o.x - 1));
    }
    double msBit = duration<double, milli>(steady_clock::now() - t0).count();
    long long stBit = steps;

    sm.assign((size_t)n * 4 + 4, 0);
    steps = 0;
    t0 = steady_clock::now();
    build(1, 1, n, a);
    for (const Op& o : ops) {
        if (o.type == 1) sAdd(1, 1, n, o.x, o.k);
        else o2.push_back(sQry(1, 1, n, o.x, o.y));
    }
    double msSeg = duration<double, milli>(steady_clock::now() - t0).count();
    long long stSeg = steps;

    bool same = (o1 == o2);

    if (csv) {
        printf("msBit,%.0f\nmsSeg,%.0f\n", msBit, msSeg);
        printf("stBit,%lld\nstSeg,%lld\n", stBit, stSeg);
        printf("same,%d\n", same ? 1 : 0);
        printf("ratioMs,%.2f\nratioSteps,%.2f\n", msSeg / max(0.001, msBit), (double)stSeg / stBit);
        printf("mem,%d\n", (int)((sm.size() * 8) / (1 << 20)));
        return 0;
    }
    printf("顶格 n = m = 5×10⁵（进程内计时，不含读入）：\n\n");
    printf("  树状数组   %5.0f ms   碰了 %10lld 个节点   数组 %d MB\n", msBit, stBit, (int)((c.size() * 8) >> 20));
    printf("  线段树     %5.0f ms   碰了 %10lld 个节点   数组 %d MB\n", msSeg, stSeg, (int)((sm.size() * 8) >> 20));
    printf("\n  秒表比 %.2f 倍，碰的节点数比 %.2f 倍；两边答案一致：%s\n",
           msSeg / max(0.001, msBit), (double)stSeg / stBit, same ? "是" : "★ 否");
    return 0;
}