This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#include "src/template.hpp"
#include "src/binary_indexed_tree.hpp"
template <class T>
struct Plus {
using value_type = T;
T operator()(const T& l, const T& r) const {
return l + r;
}
const T ide{};
};
int main() {
ll n, q;
cin >> n >> q;
BinaryIndexedTree<Plus<ll>> bit(n);
rep(i, n) {
ll a;
cin >> a;
bit.add(i, a);
}
rep(i, q) {
ll t, a, b;
cin >> t >> a >> b;
if (t == 0) {
bit.add(a, b);
} else {
cout << bit.sum(b) - bit.sum(a) << el;
}
}
}
#line 1 "test/binary_indexed_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0; i < (ll)n; i++)
#define rep3(i, l, r) for(ll i = l; i < (ll)r; i++)
#define per(i, n) for(ll i = (ll)n-1; i >= 0; i--)
#define per3(i, l, r) for(ll i = (ll)r-1; i >= (ll)l; i--)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
template<class T, class U> inline void cmax(T &a, U b) { if (a < b) a = b; }
template<class T, class U> inline void cmin(T &a, U b) { if (a > b) a = b; }
constexpr char el = '\n';
template<class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<class T, class U> istream &operator>>(istream &is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<class T> ostream &operator<<(ostream &os, const vector<T> &v) { rep(i, v.size()) os << v[i] << (i+1 != (ll)v.size() ? " " : ""); return os; }
template<class T> istream &operator>>(istream &is, vector<T> &v) { for(T &i : v) is >> i; return is; }
struct IoSetup {
IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(15); }
} io_setup;
#line 3 "src/binary_indexed_tree.hpp"
template<class ComumutativeMonoid>
struct BinaryIndexedTree {
using T = typename ComumutativeMonoid::value_type;
// 1-indexed
ll n;
vector<T> tree;
const ComumutativeMonoid ope;
BinaryIndexedTree(ll n_) : n(n_), ope(ComumutativeMonoid()) {
tree.assign(n+1, ope.ide);
}
void add(ll p, T a) {
for (ll x = p+1; x <= n; x += x&-x) {
tree[x] = ope(tree[x], a);
}
}
// sum [0, r)
T sum(ll r) const {
T sum = ope.ide;
for (ll x = r; x > 0; x -= x&-x) {
sum = ope(sum, tree[x]);
}
return sum;
}
/*
// bit[1] + bit[2] + ... + bit[x] >= w;
ll lower_bound(T w) const {
if (w <= 0) return 0;
ll x = 0, r = 1;
while (r < n) r <<= 1;
for (ll k = r; k > 0; k >>= 1){
if(x+k <= n && tree[x+k] < w){
w -= tree[x+k];
x += k;
}
}
return x+1;
}
*/
};
#line 5 "test/binary_indexed_tree.test.cpp"
template <class T>
struct Plus {
using value_type = T;
T operator()(const T& l, const T& r) const {
return l + r;
}
const T ide{};
};
int main() {
ll n, q;
cin >> n >> q;
BinaryIndexedTree<Plus<ll>> bit(n);
rep(i, n) {
ll a;
cin >> a;
bit.add(i, a);
}
rep(i, q) {
ll t, a, b;
cin >> t >> a >> b;
if (t == 0) {
bit.add(a, b);
} else {
cout << bit.sum(b) - bit.sum(a) << el;
}
}
}