树状数组

// 标准答案 —— 什么都不预处理：数组原样放着，改就直接改，查就整段扫一遍
//
// 为什么它存在：正解（树状数组）想的是「把一部分区间和攒起来，改的时候只修那几段」。
// 要是标准答案也去攒和，两份代码就是同一个思路写了两遍 ——
// 只能验出打字错误，验不出想法错误（第 9、15、34、35、36、37 章那条）。
//
// 所以这一份**一点和都不攒**：`1 p x` 就是 `a[p] += x`，`2 l r` 就是从 l 老实加到 r。
//
// ★ 扫的时候**一次 break 都没有**（第 31、35 章那条：会 break 的暴力会假装自己不慢）——
//   不过这道题的求和本来也没什么可 break 的，这里要小心的是另一件事：
//   ⚠ **不许顺手维护一个「当前总和」来加速最后那一行**，那就已经在攒和了。
//     最后一行也老老实实从 1 加到 n。
//
// 复杂度：改 O(1)、查 O(区间长度)，最坏 O(nm)。
//
// 输入：第一行 n m；第二行 a[1..n]；接下来 m 行，每行是
//       "1 p x"（a[p] += x）或 "2 l r"（输出 a[l]+…+a[r]）。
// 输出：每个 "2" 一行；★ 最后再输出一行 —— 整个数组的和 a[1]+…+a[n]。

#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);             // ★ 1 基下标（区间类题目那条约定）
    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 p; long long x;
            cin >> p >> x;
            a[p] += x;                          // 改：O(1)，这是它唯一的优点
        } else {
            int l, r;
            cin >> l >> r;
            long long s = 0;
            for (int i = l; i <= r; i++) s += a[i];   // 查：老实扫，不 break
            out += to_string(s);
            out += '\n';
        }
    }

    long long tot = 0;                          // ★ 最后那一行：也是老实从头加到尾
    for (int i = 1; i <= n; i++) tot += a[i];
    out += to_string(tot);
    out += '\n';

    cout << out;
    return 0;
}

// 第二个暴力 —— 第 6 章那份前缀和，原封不动搬过来，加上「改完整段重算」
//
// 为什么它存在（这一章的整个动机就在它身上）：
// 第 6 章章末那张表写着「只查不改用前缀和」，并且明说了它的死穴：
//
//     一旦有人改了 a[p]，s[p] 到 s[n] 全部作废，重算要 O(n)。
//
// 这一份就是把那句话**跑出来**。它和 brute.cpp 正好是一对反面：
//
//     | 做法          | 改一次   | 查一次   |
//     | brute（原数组）| O(1)     | O(区间长)|
//     | prefix（前缀和）| O(n)    | O(1)     |
//
// ★ 两份代码的输出**逐字节相同**（它们解的是同一道题），
//   所以对拍在这上面一个字都看不见 —— 第 36 章那个「第四个盲区」在这一章的第一次现场。
//   要看见差别只能换尺子：数「碰了几个格子」（见 count.cpp）。
//
// ★★ 而且这一章比第 37 章更进一步：**这两个暴力谁更烂，取决于操作配比** ——
//   全是查询时 prefix 完胜，全是修改时 brute 完胜，混着来两个一起爆。
//   所以那张耗时表**必须给出配比这个旋钮的两端**，只报一列无论报哪列都是骗人的
//   （第 35 章「必须同时给出两种形状」的同款）。
//
// 复杂度：改 O(n)、查 O(1)。

#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), s(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];      // 第 6 章那两行

    string out;
    for (int q = 0; q < m; q++) {
        int op;
        cin >> op;
        if (op == 1) {
            int p; long long x;
            cin >> p >> x;
            a[p] += x;
            for (int i = p; i <= n; i++) s[i] += x;           // ★ 死穴：后面整段全要动
        } else {
            int l, r;
            cin >> l >> r;
            out += to_string(s[r] - s[l - 1]);                // ★ 这一行是 O(1)，第 6 章的全部内容
            out += '\n';
        }
    }

    out += to_string(s[n]);                                    // 最后那一行：白送
    out += '\n';

    cout << out;
    return 0;
}

// ★ 关键一步的「看得见」版本 —— 把每个 c[i] 管辖的那一段打出来，并且**当场验证**它
//
// 为什么它存在：`lowbit` 这一章最容易变成「背两个循环」。
// 这份代码不讲循环，只讲一句话：**c[i] = a[i − lowbit(i) + 1] + … + a[i]**。
//
// ⚠ 而且它不是「打印一下」就完了（第 24 章 split.cpp 立的规矩）：
//   每一行都拿**定义**（老老实实把那一段 a 加起来）和**建树的结果**对一遍，
//   只要有一格对不上就报错退出。所以这张表既是插图，也是一次硬验证。
//
// 用法：./cover [n]        默认 n = 8（正文和动画用的就是它）
//       ./cover 16         看 16 格的样子
//
// ⚠ 输入的 a[1..n] 从 stdin 读；不给就用 1..n（这样 c[i] 的值一眼能验算）。

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

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

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 8;
    if (n < 1) n = 1;
    if (n > 64) n = 64;                                   // 这是给人看的表，不是压力测试

    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) if (!(cin >> a[i])) a[i] = i;   // 没给数据就用 1..n

    // O(n) 建树（和 fast.cpp 那三行一模一样）
    vector<long long> c(n + 2, 0);
    for (int i = 1; i <= n; i++) {
        c[i] += a[i];
        if (i + lowbit(i) <= n) c[i + lowbit(i)] += c[i];
    }

    printf("n = %d\n\n", n);
    printf("  i  二进制    lowbit   管辖的区间      长度   c[i]      验算\n");
    bool ok = true;
    for (int i = 1; i <= n; i++) {
        int lb = lowbit(i);
        int lo = i - lb + 1;
        long long s = 0;                                   // ★ 按定义老实加一遍
        for (int j = lo; j <= i; j++) s += a[j];
        if (s != c[i]) ok = false;

        string bin;
        for (int b = 5; b >= 0; b--) bin += char('0' + ((i >> b) & 1));

        char seg[32];
        snprintf(seg, sizeof(seg), "[%d, %d]", lo, i);
        printf("%3d  %s  %6d   %-14s  %4d   %-8lld  %s\n",
               i, bin.c_str(), lb, seg, lb, c[i], s == c[i] ? "✓" : "✗ 对不上");
    }

    printf("\n★ 长度那一列就是 lowbit(i) —— c[i] 攒的东西**正好只有 lowbit(i) 那么长**。\n");
    printf("  对照第 6 章的前缀和：那里每个 s[i] 都从 1 攒到 i（长度 i），所以改一个数要动一大片。\n");

    // 顺带把「查前缀和」那条路也打出来：它的长度正好是二进制里 1 的个数
    printf("\n查前缀和 sum(r) 走过的格子（★ 长度 = r 的二进制里 1 的个数）\n");
    for (int r = 1; r <= n; r++) {
        printf("  sum(%2d) = ", r);
        int cnt = 0;
        for (int i = r; i > 0; i -= lowbit(i)) { printf("%sc[%d]", cnt ? " + " : "", i); cnt++; }
        printf("%*s（%d 格，popcount(%d) = %d）\n", max(0, 30 - cnt * 7), "", cnt, r, __builtin_popcount(r));
        if (cnt != __builtin_popcount(r)) ok = false;
    }

    // 改 a[p] 那条路
    printf("\n改 a[p] 要跟着动的格子（★ 每一步最低位的 1 都严格往高位挪）\n");
    for (int p = 1; p <= n; p++) {
        printf("  add(%2d): ", p);
        int cnt = 0, last = 0;
        for (int i = p; i <= n; i += lowbit(i)) {
            printf("%sc[%d]", cnt ? " → " : "", i);
            if (cnt && lowbit(i) <= last) ok = false;      // 硬验证：lowbit 必须严格变大
            last = lowbit(i); cnt++;
        }
        printf("%*s（%d 格）\n", max(0, 30 - cnt * 7), "", cnt);
    }

    printf("\n%s\n", ok ? "✓ 全部验算通过（定义 / popcount / lowbit 严格递增，三件都对上了）"
                        : "✗ 有对不上的，上面标出来了");
    return ok ? 0 : 1;
}

// 正解 —— 树状数组（Fenwick Tree）：**可以修改的前缀和**
//
// ============ ★ 关键一步：c[i] 到底管哪一段 ============
//
//   lowbit(i) = i & -i  —— i 的二进制里**最低位的那个 1**（连同它后面的 0）。
//   例如 lowbit(6) = lowbit(0b110) = 0b10 = 2，lowbit(8) = 8，lowbit(7) = 1。
//
//   ★ 定义：**c[i] = a[i − lowbit(i) + 1] + … + a[i]**，也就是以 i 结尾、长 lowbit(i) 的那一段。
//     写成区间就是 **(i − lowbit(i), i]**。
//
//     i :  1    2      3    4        5    6      7    8
//     管:  [1] [1,2]  [3] [1,4]     [5] [5,6]  [7] [1,8]
//     长:  1    2      1    4        1    2      1    8      ← 正好是 lowbit(i)
//
//   第 6 章的前缀和是「每个 s[i] 都从头攒到 i」，所以改一个数要动后面**所有**格子。
//   树状数组只攒 lowbit(i) 那么长的一段 —— **攒得少，所以改得起**。
//   ⚠ 而这正是第 6 章章末那张表许下的那句话：又改又查的时候，
//     要的不是「更快的前缀和」，是**能改的**前缀和。
//
// ============ 两条路：为什么一个 += 一个 −= ============
//
//   ① 查前缀和 sum(r) = a[1]+…+a[r]：
//      c[r] 已经管住了 (r − lowbit(r), r]，剩下的是 (0, r − lowbit(r)] ——
//      **同一个问题，规模变小了**（第 1、2 章那句「把大问题切成同形状的小问题」）。
//      于是 `for (i = r; i > 0; i -= lowbit(i)) s += c[i];`
//
//      ★ 这一句 `i -= lowbit(i)` 干的事是「**抹掉二进制里最低位的那个 1**」，
//        所以循环转的圈数 **恰好等于 r 的二进制里 1 的个数**（popcount(r)）——
//        ⚠ 注意这不是「不超过」，是**等号**。它 ≤ ⌊log₂ r⌋ + 1，于是 O(log n)。
//
//   ② 改 a[p] += x：所有**管到 p** 的 c[i] 都要跟着加 x。
//      哪些 i 管到 p？答案是 p, p+lowbit(p), 那个再 +lowbit, …（证明见下面 ⚠）
//      于是 `for (i = p; i <= n; i += lowbit(i)) c[i] += x;`
//
//      ★ 这一句 `i += lowbit(i)` 干的事是「**进位**」：设 lowbit(i) = 2^k，
//        那么 i 的第 k 位是 1，加上 2^k 必然往上进位，第 k 位（和它上面那串连续的 1）全变成 0 ——
//        所以**新的 lowbit 严格比旧的大**。最低位的 1 一路往高位挪，
//        最多挪 ⌊log₂ n⌋ + 1 次就超过 n 了，于是也是 O(log n)。
//
//   ⚠ 为什么「管到 p 的 c[i]」正好是那条路？两句话：
//     · 每一步都合法：c[i] 管 (i−lowbit(i), i]，而 i' = i + lowbit(i) 管 (i'−lowbit(i'), i']，
//       因为 lowbit(i') > lowbit(i) 且 i' − lowbit(i') < i − lowbit(i) < p ≤ i < i'，所以 i' 也管着 p；
//     · 一个都不漏：设 j 管着 p 且 j > i，那 j 的区间 (j−lowbit(j), j] 完整地盖住 i 所在的位置，
//       于是 j ≥ i'（区间要么套住、要么不相交，不会「半重叠」—— 这是 lowbit 结构最关键的性质）。
//
//   ⇒ **改 O(log n)、查 O(log n)。两边同时是 log —— 这就是它比那两个暴力强的全部原因。**
//     （第 37 章那句「堆赢在两列同时是 O(log n)」的同款：它只攒「刚好够用的那点和」。）
//
// ============ ★ 建树只要 O(n)，不用做 n 次 add ============
//
//   c[i] 管的那一段 = a[i] 加上「它下面挂着的几个子段」。
//   顺着 i 从小到大扫，先把 a[i] 放进 c[i]，再把 c[i] 整个交给它爸爸 i + lowbit(i) ——
//   一遍扫完就建好了（见 main 里那三行）。
//   ★ 这和「做 n 次 add」的结果**完全一样**（buildSlow.cpp 300 轮逐字节验过），
//     只是后者要 O(n log n)。⚠ 对拍在这上面一个字都看不见 —— 又一个「只影响复杂度」的写法。
//
// 复杂度 O((n + m) log n)。

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

const int MAXN = 200005;
long long c[MAXN];                              // ★ c[1..n]，c[0] 空着不用（1 基下标）
int n, m;

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

/** a[p] += x：沿着「进位」那条路往上，每一格都加 x */
void add(int p, long long x) {
    for (int i = p; i <= n; i += lowbit(i)) c[i] += x;   // ⚠ 是 i <= n，不是 i < n
}

/** 前缀和 a[1]+…+a[r]：沿着「抹掉最低位的 1」那条路往下，转 popcount(r) 圈 */
long long sum(int r) {
    long long s = 0;
    for (int i = r; i > 0; i -= lowbit(i)) s += c[i];    // ⚠ 是 i > 0，不是 i > 1
    return s;
}

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

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

    // ★ O(n) 建树：a[i] 先落进 c[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 p; long long x;
            cin >> p >> x;
            add(p, x);
        } else {
            int l, r;
            cin >> l >> r;
            out += to_string(sum(r) - sum(l - 1));   // ⚠ 是 l-1，不是 l（区间和 = 两个前缀和相减）
            out += '\n';
        }
    }

    out += to_string(sum(n));                        // ★ 最后那一行：整个数组的和
    out += '\n';

    cout << out;
    return 0;
}

// 错误版本① —— 两条路的方向记反了：add 往下走、query 往上走
//
// 只改了两个符号（`+=` ↔ `-=`），是初学树状数组最常见的手滑。
// ⚠ 它甚至不会崩、不会死循环，边界条件照抄过来还挺像回事。
//
// ★ 它靠什么现形：几乎什么数据都行 —— 这一份是这一章的**基线**，
//   用来说明「抓得住它」根本不能证明生成器够狠（第 31 章那份 wrongIdentity 的同款用途）。

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

const int MAXN = 200005;
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 > 0; i -= lowbit(i)) c[i] += x;   // ✗ 方向反了
}

long long sum(int r) {
    long long s = 0;
    // ✗ 方向反了。⚠ 这里多写了个 `i > 0`：因为 lowbit(0) = 0，
    //   区间查询里 sum(l-1) 在 l = 1 时会传进来一个 0，光写 `i <= n` 会**原地死循环**。
    //   （对拍里挂一个死循环的程序，整张表就再也跑不完了 —— 错误版本也得能跑完。）
    for (int i = r; i > 0 && i <= n; i += lowbit(i)) s += c[i];
    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++) {
        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 p; long long x;
            cin >> p >> x;
            add(p, x);
        } else {
            int l, r;
            cin >> l >> r;
            out += to_string(sum(r) - sum(l - 1));
            out += '\n';
        }
    }

    out += to_string(sum(n));
    out += '\n';

    cout << out;
    return 0;
}

// 错误版本② —— add 的循环条件写成 `i < n`（差一，漏掉最后那一格 c[n]）
//
// ★★ 它靠什么现形：**n 的二进制形状** —— 这是这一章全新的一类旋钮，
//    前 37 章的旋钮都是「值域 / 规模 / 结构角色 / 操作序列」，没有一个是**下标的二进制位**。
//
//   · add(p) 那条路会不会经过 n？c[n] 管的是 (n − lowbit(n), n]，
//     所以**当且仅当 p > n − lowbit(n)**。于是：
//       n = 2^k（比如 8、16）→ lowbit(n) = n → **每一个 p 都经过 n**，必漏；
//       n 是奇数（lowbit = 1）→ 只有 p = n 才经过，概率 1/n。
//   · 漏了之后还得有人去读 c[n] 才看得出来：sum(r) 的路从 r 出发，
//     **只有 r = n 时才碰得到 c[n]**。
//
//   ⇒ ★ 所以题面最后那一行「整个数组的和」（= sum(n)）**正好是唯一保证 r = n 的那次查询** ——
//     它是专门为这个 bug 准备的一条腿（第 35、36、37 章那条「题面多问一句」的第四次）。

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

const int MAXN = 200005;
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;   // ✗ 应该是 i <= n
}

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;

    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 p; long long x;
            cin >> p >> x;
            add(p, x);
        } else {
            int l, r;
            cin >> l >> r;
            out += to_string(sum(r) - sum(l - 1));
            out += '\n';
        }
    }

    out += to_string(sum(n));
    out += '\n';

    cout << out;
    return 0;
}

// 错误版本③ —— query 里 lowbit 的参数写成了 r，没跟着 i 变
//
//     for (int i = r; i > 0; i -= lowbit(r))     ✗    // 应该是 lowbit(i)
//
// 复制粘贴 / 手快时最容易漏掉的一个字母，编译器一声不吭。
//
// ★★ 它靠什么现形：**r 的二进制形状** —— 而且条件干净得可以直接写出来：
//   这份代码每次都减掉同一个数 lowbit(r)，于是它加的是 c[r] + c[r−lowbit(r)] + c[r−2·lowbit(r)] + …
//   · **r 是 2 的幂**时 lowbit(r) = r，一步就减到 0 —— 它加的正好只有 c[r]，**完全正确**；
//   · r 不是 2 的幂时它会多加一堆本不该加的格子（r = 7 时把 c[1..7] 全加了一遍）。
//
//   ⇒ ★★ **它和 wrongEnd 想要的东西正好相反**：
//     wrongEnd 要 n = 2^k（add 那条路才必经 c[n]），wrongVar 要 r ≠ 2^k（不然它是对的）。
//     ⚠ 所以 n **不能只造 2 的幂，也不能一个 2 的幂都不造** ——
//     生成器里 n 从 {2^k, 2^k−1, 2^k+1} 三选一，就是为了这一对拉扯
//     （第 31 章那条「两头都要看：某一支永远走不到是坑，某一支占得太多也是坑」）。

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

const int MAXN = 200005;
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;
    // ⚠ r = 0 时 lowbit(r) = 0，`i > 0` 那句在 i = 0 时就已经不成立，所以不会死循环。
    for (int i = r; i > 0; i -= lowbit(r)) s += c[i];   // ✗ 应该是 lowbit(i)
    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++) {
        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 p; long long x;
            cin >> p >> x;
            add(p, x);
        } else {
            int l, r;
            cin >> l >> r;
            out += to_string(sum(r) - sum(l - 1));
            out += '\n';
        }
    }

    out += to_string(sum(n));
    out += '\n';

    cout << out;
    return 0;
}

// 错误版本④ —— 区间和写成 `sum(r) − sum(l)`（少减了一格，把 a[l] 也扣掉了）
//
// 这是第 6 章那条「区间和 = s[r] − s[l−1]」的老账，换个壳又来一次。
//
// ★ 它靠什么现形：**a[l] ≠ 0**。
//   ⚠ 而「a[l] 是不是 0」几乎完全由生成器决定 ——
//     顺手让初始数组全 0、又只做几次修改的话，随便挑一个 l 大概率就是 0，
//     这个 bug 当场隐身。（这一章「顺手写法」踩的坑之一，见 gen.cpp 档位 1。）
//   · 另外 l = 1 时它算的是 sum(r) − sum(1)，同样错 —— 所以边界那一端不用特别造。

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

const int MAXN = 200005;
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);
    cin.tie(nullptr);

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

    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 p; long long x;
            cin >> p >> x;
            add(p, x);
        } else {
            int l, r;
            cin >> l >> r;
            out += to_string(sum(r) - sum(l));           // ✗ 应该是 sum(l - 1)
            out += '\n';
        }
    }

    out += to_string(sum(n));
    out += '\n';

    cout << out;
    return 0;
}

// 错误版本⑤ —— 建树时直接把 a[i] 塞进 c[i]（把树状数组当成了原数组）
//
// 这是「以为 c[] 就是 a[] 换了个名字」的典型症状：`add` / `sum` 两个函数都抄对了，
// 唯独初始化那一行想当然。⚠ 而它跑起来一点异常都没有 —— 只是所有答案都偏小。
//
// ★ 它靠什么现形：**初始数组不能全是 0**。
//   ⚠⚠ 而这正是这一章「顺手写法」的现场（第 27–34、37 章连着九次的那条）：
//     随手写生成器时最自然的做法就是「数组从全 0 开始，反正要什么值都能加出来」——
//     题面明明写着 |a_i| ≤ 10⁹（0 只是其中一个值），生成器却替题目做了主。
//   实测：顺手那一档它是 **0 / 300**（第十次）。

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

const int MAXN = 200005;
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);
    cin.tie(nullptr);

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

    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        c[i] = x;                                  // ✗ c[i] 不是 a[i]，它管的是一整段
    }

    string out;
    for (int q = 0; q < m; q++) {
        int op;
        cin >> op;
        if (op == 1) {
            int p; long long x;
            cin >> p >> x;
            add(p, x);
        } else {
            int l, r;
            cin >> l >> r;
            out += to_string(sum(r) - sum(l - 1));
            out += '\n';
        }
    }

    out += to_string(sum(n));
    out += '\n';

    cout << out;
    return 0;
}

// 错误版本⑥ —— c[] 忘了开 long long
//
// ★★ 它靠什么现形：**没有任何生成器能靠随机对拍抓住它**（第 35 章那条的第二次现场）。
//   小数据上它 300 轮逐字节全对；只有当**部分和真的超过 2^31** 时才会翻车，
//   而这个条件和「对拍要造小数据」是天生矛盾的。
//
// ⚠ 而且和第 35 章一模一样：溢出之后的那个数**不是负数，是个「看着挺正常」的数** ——
//   n = 2×10⁵、每个都是 10⁹ 时正解给 2×10¹⁴，它给一个几位数的东西，
//   不看正确答案根本不会起疑。
//
// **这只能靠脑子，不能靠对拍**：写之前先估一估「和最大能到多少」。
//   这道题：2×10⁵ × 10⁹ = 2×10¹⁴ —— int 装不下（上限约 2.1×10⁹），必须 long long。

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

const int MAXN = 200005;
int c[MAXN];                                    // ✗ 应该是 long long
int n, m;

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

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

int sum(int r) {
    int 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;

    for (int i = 1; i <= n; i++) {
        int 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 p, x;
            cin >> p >> x;
            add(p, x);
        } else {
            int l, r;
            cin >> l >> r;
            out += to_string(sum(r) - sum(l - 1));
            out += '\n';
        }
    }

    out += to_string(sum(n));
    out += '\n';

    cout << out;
    return 0;
}

// 正解 —— 树状数组（Fenwick Tree）：**可以修改的前缀和**
//
// ============ ★ 关键一步：c[i] 到底管哪一段 ============
//
//   lowbit(i) = i & -i  —— i 的二进制里**最低位的那个 1**（连同它后面的 0）。
//   例如 lowbit(6) = lowbit(0b110) = 0b10 = 2，lowbit(8) = 8，lowbit(7) = 1。
//
//   ★ 定义：**c[i] = a[i − lowbit(i) + 1] + … + a[i]**，也就是以 i 结尾、长 lowbit(i) 的那一段。
//     写成区间就是 **(i − lowbit(i), i]**。
//
//     i :  1    2      3    4        5    6      7    8
//     管:  [1] [1,2]  [3] [1,4]     [5] [5,6]  [7] [1,8]
//     长:  1    2      1    4        1    2      1    8      ← 正好是 lowbit(i)
//
//   第 6 章的前缀和是「每个 s[i] 都从头攒到 i」，所以改一个数要动后面**所有**格子。
//   树状数组只攒 lowbit(i) 那么长的一段 —— **攒得少，所以改得起**。
//   ⚠ 而这正是第 6 章章末那张表许下的那句话：又改又查的时候，
//     要的不是「更快的前缀和」，是**能改的**前缀和。
//
// ============ 两条路：为什么一个 += 一个 −= ============
//
//   ① 查前缀和 sum(r) = a[1]+…+a[r]：
//      c[r] 已经管住了 (r − lowbit(r), r]，剩下的是 (0, r − lowbit(r)] ——
//      **同一个问题，规模变小了**（第 1、2 章那句「把大问题切成同形状的小问题」）。
//      于是 `for (i = r; i > 0; i -= lowbit(i)) s += c[i];`
//
//      ★ 这一句 `i -= lowbit(i)` 干的事是「**抹掉二进制里最低位的那个 1**」，
//        所以循环转的圈数 **恰好等于 r 的二进制里 1 的个数**（popcount(r)）——
//        ⚠ 注意这不是「不超过」，是**等号**。它 ≤ ⌊log₂ r⌋ + 1，于是 O(log n)。
//
//   ② 改 a[p] += x：所有**管到 p** 的 c[i] 都要跟着加 x。
//      哪些 i 管到 p？答案是 p, p+lowbit(p), 那个再 +lowbit, …（证明见下面 ⚠）
//      于是 `for (i = p; i <= n; i += lowbit(i)) c[i] += x;`
//
//      ★ 这一句 `i += lowbit(i)` 干的事是「**进位**」：设 lowbit(i) = 2^k，
//        那么 i 的第 k 位是 1，加上 2^k 必然往上进位，第 k 位（和它上面那串连续的 1）全变成 0 ——
//        所以**新的 lowbit 严格比旧的大**。最低位的 1 一路往高位挪，
//        最多挪 ⌊log₂ n⌋ + 1 次就超过 n 了，于是也是 O(log n)。
//
//   ⚠ 为什么「管到 p 的 c[i]」正好是那条路？两句话：
//     · 每一步都合法：c[i] 管 (i−lowbit(i), i]，而 i' = i + lowbit(i) 管 (i'−lowbit(i'), i']，
//       因为 lowbit(i') > lowbit(i) 且 i' − lowbit(i') < i − lowbit(i) < p ≤ i < i'，所以 i' 也管着 p；
//     · 一个都不漏：设 j 管着 p 且 j > i，那 j 的区间 (j−lowbit(j), j] 完整地盖住 i 所在的位置，
//       于是 j ≥ i'（区间要么套住、要么不相交，不会「半重叠」—— 这是 lowbit 结构最关键的性质）。
//
//   ⇒ **改 O(log n)、查 O(log n)。两边同时是 log —— 这就是它比那两个暴力强的全部原因。**
//     （第 37 章那句「堆赢在两列同时是 O(log n)」的同款：它只攒「刚好够用的那点和」。）
//
// ============ ★ 建树只要 O(n)，不用做 n 次 add ============
//
//   c[i] 管的那一段 = a[i] 加上「它下面挂着的几个子段」。
//   顺着 i 从小到大扫，先把 a[i] 放进 c[i]，再把 c[i] 整个交给它爸爸 i + lowbit(i) ——
//   一遍扫完就建好了（见 main 里那三行）。
//   ★ 这和「做 n 次 add」的结果**完全一样**（buildSlow.cpp 300 轮逐字节验过），
//     只是后者要 O(n log n)。⚠ 对拍在这上面一个字都看不见 —— 又一个「只影响复杂度」的写法。
//
// 复杂度 O((n + m) log n)。

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

const int MAXN = 200005;
long long c[MAXN];                              // ★ c[1..n]，c[0] 空着不用（1 基下标）
int n, m;

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

/** a[p] += x：沿着「进位」那条路往上，每一格都加 x */
void add(int p, long long x) {
    for (int i = p; i <= n; i += lowbit(i)) c[i] += x;   // ⚠ 是 i <= n，不是 i < n
}

/** 前缀和 a[1]+…+a[r]：沿着「抹掉最低位的 1」那条路往下，转 popcount(r) 圈 */
long long sum(int r) {
    long long s = 0;
    for (int i = r; i > 0; i -= lowbit(i)) s += c[i];    // ⚠ 是 i > 0，不是 i > 1
    return s;
}

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

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

    // ★ O(n) 建树：a[i] 先落进 c[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 p; long long x;
            cin >> p >> x;
            add(p, x);
        } else {
            int l, r;
            cin >> l >> r;
            out += to_string(sum(r) - sum(l - 1));   // ⚠ 是 l-1，不是 l（区间和 = 两个前缀和相减）
            out += '\n';
        }
    }

    out += to_string(sum(n));                        // ★ 最后那一行：整个数组的和
    out += '\n';

    cout << out;
    return 0;
}

// ★ 跨章节：用树状数组重做一遍第 11 章的逆序对
//
// 第 11 章是「归并排序顺手数出来」（分治）。这一份是**完全不同的思路**：
//
//     从左往右扫，扫到 a[j] 时问一句：**前面已经放进去的数里，有几个比它大？**
//     那些数的下标都比 j 小、值都比 a[j] 大 —— 每一个都是一个逆序对。
//
//   「前面放进去的数里有几个 ≤ 某个值」正好是一句**前缀和**，
//   而「放进去一个数」正好是一次**单点 +1** —— 又改又查，正是这一章的题。
//
//     前面比 a[j] 大的个数 = (已经放进去的个数) − (已经放进去的 ≤ a[j] 的个数)
//                          = (j − 1) − sum(rank[j])
//
// ★ 「相等不算逆序对」这件事就藏在 sum 的那个 ≤ 里（第 22 章 lower/upper_bound
//   一个字母之差的同款）：sum 数的是 **≤ a[j]**，减掉之后剩下的才是**严格大于**。
//   ⚠ 把它写成「< a[j]」的话，相等的那些会被算成逆序对 —— 而第 11 章的生成器
//     一半的数取自 0..5，重复元素多得很，这个错当场就会被打出来。
//
// ============ 为什么要离散化 ============
//
//   树状数组的下标是「位置」，这里我们要拿**值**当下标。可值可以是负数、可以很大 ——
//   所以先把所有值排序去重，用「它排第几」（rank，从 1 开始）代替原值。
//   ★ 只比较大小的题，换成 rank 不影响任何答案。
//
// 输入 / 输出**和第 11 章一字不差**（第一行 n，第二行 n 个整数；输出逆序对个数），
// 所以它和第 11 章的 brute.cpp / fast.cpp 可以直接三方对拍，**生成器也用第 11 章那份**。
//
// 复杂度 O(n log n) —— 和归并那份同级，但常数和思路都不一样。

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

int n;
vector<int> c;

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

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

int sum(int r) {
    int 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);

    int len;
    if (!(cin >> len)) return 0;

    vector<long long> a(len);
    for (int i = 0; i < len; i++) cin >> a[i];

    // 离散化：值 → 它在去重排序后的位置（1 基）
    vector<long long> srt = a;
    sort(srt.begin(), srt.end());
    srt.erase(unique(srt.begin(), srt.end()), srt.end());
    n = (int)srt.size();
    c.assign(n + 2, 0);

    long long cnt = 0;                              // ⚠ 最多 n(n−1)/2，一律 long long
    for (int j = 0; j < len; j++) {
        int rk = (int)(lower_bound(srt.begin(), srt.end(), a[j]) - srt.begin()) + 1;
        cnt += (long long)j - sum(rk);              // 前面比 a[j] 严格大的个数
        add(rk, 1);
    }

    cout << cnt << "\n";
    return 0;
}