一、题目

二、题解：

2.1：题目的修改/查询交替进行，一眼就是树状数组的模板题目(当先修改最后查询可以使用前缀和/差分实现)，

2.2：树状数组结构：每一个节点都有其管辖区间

2.2.1:lowbit()函数 : $lowbit(x)$ = $x$ & ^$x$

• 例如：
  
• 此时，$lowbit(i)$的管辖区间长度为$lowbit(i)$
  

2.3:树状数组的修改（单点修改）

• 1、假设，我们现在修改$a3$这个节点，我们可以发现其会影响的区间
  
• 2、仔细观察可以发现，刚好每一个节点到下一个节点是$i+lowbit(i)$，
• 同理以$a5$举例：代码如下
  

void update(ll x, ll v)   //第 x 个值变化了 v
{for (int i = x; i <= n; i += lowbit(i)){t[i] += v;}
}

2.4:树状数组的查询

• 1、假设我们现在以$a7$为标准，查询$a7$的值
• 那么此时，我们需要找看看哪些区间可以拼接成$a7$，可以发现刚好是$i-lowbit(i)$

t7-->t6-->t4

ll getsum(ll x)   //区间查询
{ll sum = 0;for (int i = x; i >= 1 ; i-=lowbit(i)){sum += t[i];}return sum;
}

3、完整代码如下：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int N = 3e5 + 7;
ll a[N];
ll t[N];   //树状数组
ll n, q;ll lowbit(ll x)   //树状数组底层函数
{return x & -x;
}void update(ll x, ll v)   //第 x 个值变化了 v
{for (int i = x; i <= n; i += lowbit(i)){t[i] += v;}
}ll getsum(ll x)   //区间查询
{ll sum = 0;for (int i = x; i >= 1 ; i-=lowbit(i)){sum += t[i];}return sum;
}void solve()
{cin >> n >> q ;for (int i = 1; i <= n; i++) cin >> a[i];//初始化树状数组for (int i = 1; i <= n; i++) update(i, a[i]);while (q--) //q次询问{ll op; cin >> op;if (op == 1){ll k, v; cin >> k >> v;update(k, v);}else{ll l, r; cin >> l >> r;cout << getsum(r) - getsum(l - 1) << '\n';}}//for(int i=1;i<=n;i++) cout<<t[i]<<' ';
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int _ = 1; //cin >> _;while (_--) solve();system("pause");return 0;
}