洛谷 P3368 【模板】树状数组 2

// P3368 第 ① 版：**题目怎么说就怎么做** —— 区间加就一个一个加，单点查就直接看
//
// ★ 它值多少分，题面自己写着：
//     · 「对于 30% 的数据：N ≤ 8，M ≤ 10」  ⇒ 80 次加法，★ 稳拿 30 分；
//     · 「对于 70% 的数据：N, M ≤ 10⁴」     ⇒ 最坏 10⁸ 次，本机约 0.03 秒 ⇒ ★ 也过得去；
//     · 顶格 N = M = 5×10⁵                 ⇒ **2.5×10¹¹ 次**，时限 1 秒。
//
// ⚠ 注意它和上一道题的暴力**慢在相反的地方**：
//   [P3374](/sol/p3374/) 的暴力是「改得快、查得慢」，这一版是「**查得快、改得慢**」。

#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 + 2, 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, y; long long k;
            cin >> x >> y >> k;
            for (int i = x; i <= y; i++) a[i] += k;    // ⚠ 一个一个加
        } else {
            int x;
            cin >> x;
            out += to_string(a[x]);                    // ★ 查：一句话
            out += '\n';
        }
    }
    cout << out;
    return 0;
}

// P3368 第 ② 版：**纯差分数组** —— 第 6 章那招原样搬过来
//
//   d[x] += k、d[y+1] −= k        ⇒ 区间加变成两格，O(1)
//   a[x] = d[1] + … + d[x]        ⇒ ⚠ 每问一次就要现算一遍前缀和，O(n)
//
// ★ 它是**对的**（对拍 300 轮逐字节相同），而且比第 ① 版强一头：
//   第 ① 版慢在「改」，这一版把改压到了 O(1) —— 但它把慢挪到了「查」上。
//
// ⚠ 顶格 M 次询问 × O(n) = 2.5×10¹¹，还是过不去。
//   ⇒ ★★ 这一版才是这道题真正的台阶：**它证明了「差分」这一步是对的，
//     缺的只是「怎么把那个前缀和也变快」** —— 而那正好是树状数组的定义。
//   ⇒ 第 ③ 版把 d 交给树状数组，两边同时变成 O(log n)，就 AC 了。

#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> d(n + 2, 0);
    long long prev = 0;
    for (int i = 1; i <= n; i++) { long long x; cin >> x; d[i] = x - prev; prev = x; }

    string out;
    for (int q = 0; q < m; q++) {
        int op;
        cin >> op;
        if (op == 1) {
            int x, y; long long k;
            cin >> x >> y >> k;
            d[x] += k;
            d[y + 1] -= k;                              // ⚠ 数组要开到 n+1
        } else {
            int x;
            cin >> x;
            long long s = 0;
            for (int i = 1; i <= x; i++) s += d[i];     // ⚠ 每次都从头攒一遍
            out += to_string(s);
            out += '\n';
        }
    }
    cout << out;
    return 0;
}

// P3368【模板】树状数组 2 —— ★ 这一版就能 AC（区间加 + 单点查）
//
// ============ ★★★ 关键一步：把树状数组建在**差分数组**上 ============
//
//   上一道 [P3374](/sol/p3374/) 是「单点加 + 区间和」，这道题**正好反过来**：
//   「区间加 + 单点查」。而这两件事之间隔着的，正是第 6 章那对逆运算：
//
//       d[i] = a[i] − a[i−1]           （差分）
//       a[x] = d[1] + d[2] + … + d[x]  （前缀和）
//
//   ⇒ 「给 [x, y] 每个数加 k」在 d 上只动**两格**：d[x] += k、d[y+1] −= k；
//   ⇒ 「问 a[x] 是多少」在 d 上就是**前缀和 sum(x)**。
//
//   ⇒ ★★ 于是这道题和上一道用的是**同一份树状数组代码，一个字都不用改** ——
//     换掉的只是「喂给它的数组是谁」：上一道喂 a，这一道喂 d。
//     （这也是本章第 ⑦ 步那句「树状数组维护的是**你选的那个数组**的前缀和」的现场。）
//
// ============ ⚠ 为什么必须是树状数组，第 6 章那招不够 ============
//
//   第 6 章 [P2367](/sol/p2367/) 也是「区间加」，那里**纯差分数组就够了** ——
//   因为那道题**所有修改做完之后才问一次**，最后统一还原一遍 O(n) 就完事。
//   这道题的修改和询问是**穿插**的（第 ③ 步量了：随机数据里「所有修改都排在所有询问之前」
//   的概率是多少），⇒ 每问一次就得现算一遍前缀和 O(n) ⇒ 顶格 2.5×10¹¹。
//   ⇒ **差的那三个字就是「可修改」。**
//
// ⚠ 为什么是 long long：题面保证「任意时刻序列中任意元素的绝对值都不大于 2³⁰」
//   ⇒ |d[i]| = |a[i] − a[i−1]| 最大到 **2³¹**，而 int 的上限是 2³¹ − 1 ——
//   **正好差 1**（第 ④ 步：这条线只有一个点宽）。

#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) {
    if (p > n) return;                                  // ⚠ y = n 时 y+1 会越界，这里挡掉
    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);
    cin.tie(nullptr);

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

    // ★ O(n) 建树，喂进去的是**差分** d[i] = a[i] − a[i−1]
    long long prev = 0;
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        c[i] += x - prev;
        prev = 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;                                      // ⚠ 每行 2 个还是 4 个数，由它说了算
        if (op == 1) {
            int x, y; long long k;
            cin >> x >> y >> k;
            add(x, k);
            add(y + 1, -k);
        } else {
            int x;
            cin >> x;
            out += to_string(sum(x));
            out += '\n';
        }
    }
    cout << out;
    return 0;
}