树状数组

题目描述

给定数列 $a_1, a_2, \dots, a_n$，你需要依次进行 $q$ 个操作，操作有两类：

• 1 i x：给定 $i,x$，将 $a_i$ 加上 $x$；
• 2 l r：给定 $l,r$，求 $\sum_{i=l}^r a_i$ 的值（换言之，求 $a_l+a_{l+1}+\dots+a_r$ 的值）。

输入格式

第一行包含 $2$ 个正整数 $n,q$，表示数列长度和询问个数。保证 $1\le n,q\le 10^6$。第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示初始数列。保证 $|a_i|\le 10^6$。接下来 $q$ 行，每行一个操作，为以下两种之一：

• 1 i x：给定 $i,x$，将 $a[i]$ 加上 $x$；
• 2 l r：给定 $l,r$，求 $\sum_{i=l}^r a_i$ 的值。

保证 $1\leq l\leq r\leq n,$ $|x|\le 10^6$。

输出格式

对于每个 2 l r 操作输出一行，每行有一个整数，表示所求的结果。

样例

输入样例

3 2
1 2 3
1 2 0
2 1 3

输出样例

6

数据范围

对于所有数据，$1\le n,q\le 10^6,$ $|a_i|\le 10^6$, $1\le l\le r\le n,$ $|x|\le 10^6$。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000002
#define ll long long
ll bit[MAXN], n, q, t, a, b;

inline ll sum(ll i) {
    ll s = 0;
    while (i > 0) {
        s += bit[i];
        i -= i & -i;
    }
    return s;
}

inline void add(ll i, const ll& x) {
    while (i <= n) {
        bit[i] += x;
        i += i & -i;
    }
}

inline void op(const ll& type, const ll& a, const ll& b) {
    switch (type) {
        case 1:
            add(a, b);
            break;
        case 2:
            printf("%lld\n", sum(b) - sum(a - 1));
            break;
    }
}

int main() {
    scanf("%lld%lld", &n, &q);
    for (ll i = 1; i <= n; ++i)
        scanf("%lld", &a), add(i, a);
    for (ll i = 1; i <= q; ++i)
        scanf("%lld%lld%lld", &t, &a, &b), op(t, a, b);
}