Dynamic Range Sum Queries

1#include<bits/stdc++.h>
2using namespace std;
3#define int long long
4
5const int MAXN = 200005;
6int N, Q, fw[MAXN];
7
8void add(int idx, int v) {
9  for (++idx; idx <= N; idx += idx & -idx)
10    fw[idx] += v;
11}
12int sum(int idx) {
13  int ret = 0;
14  for (++idx; idx > 0; idx -= idx & -idx)
15    ret += fw[idx];
16  return ret;
17}
18int sum(int l, int r) {
19  return sum(r) - sum(l - 1);
20}
21
22signed main(){
23  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
24  
25  cin >> N >> Q;
26
27  int A[N];
28  for (int i = 0; i < N; ++i) {
29    cin >> A[i];
30    add(i, A[i]);
31  }
32
33  while (Q--) {
34    int t; cin >> t;
35    if (t == 1) {
36      int k, u;
37      cin >> k >> u; --k;
38      add(k, u - A[k]);
39      A[k] = u;
40    } else if (t == 2) {
41      int a, b;
42      cin >> a >> b; --a, --b;
43      cout << sum(a, b) << '\n';
44    }
45  }
46  return 0;
47}