【树状数组】Dynamic Range Sum Queries
题目翻译
给定一个包含 n 个整数的数组，你的任务是处理 q 个以下类型的查询：
- 更新位置 k 的值为 u
- 计算区间 [a, b] 内所有值的总和
输入说明
- 第一行输入两个整数 n 和 q：分别表示数组中元素的数量和查询的数量。
- 第二行输入 n 个整数 x₁, x₂, ..., xₙ：表示数组的元素。
- 接下来 q 行描述查询，每行包含三个整数：
- 若为 "1 k u"：表示将数组中位置 k 的元素更新为 u。
- 若为 "2 a b"：表示查询数组中区间 [a, b] 内所有元素的总和。
约束条件
- 1 ≤ n, q ≤ 2×10⁵
- 1 ≤ xᵢ, u ≤ 10⁹
- 1 ≤ k ≤ n
- 1 ≤ a ≤ b ≤ n
输出说明
对于每个类型为 "2 a b" 的查询，输出对应的区间总和。
样例输入
复制
8 4 3 2 4 5 1 1 5 3 2 1 4 2 5 6 1 3 1 2 1 4样例输出
复制
14 2 11
树状数组的核心思想
树状数组通过二进制分解来组织数据，用一个数组 tree 表示，其中每个元素 tree[i] 并不直接对应原始数组的元素，而是存储原始数组中某段连续区间的和。
每个 tree[i] 管理的范围和 i 的二进制有关：
i=1（二进制1）：管理 1 个数（自己）i=2（二进制10）：管理 2 个数（1-2）i=3（二进制11）：管理 1 个数（3）i=4（二进制100）：管理 4 个数（1-4）
i & -i 是什么
在计算机中，整数以二进制补码形式存储，-i 等价于 ~i + 1（按位取反再加 1）。
i & -i 的结果是：保留 i 的二进制中最低位的 1，其余位都变为 0。
i += i & -i 的作用
这个操作的本质是：让 i 跳到下一个需要更新的父节点。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;struct bit{vector<ll>arr;vector<ll>tree;int n;bit(int size){n=size;arr.resize(n+1,0);tree.resize(n+1,0);}void add(int idx,ll val){while(idx<=n)tree[idx]+=val,idx+=idx&-idx;}void update(int idx,ll val){ll delta=val-arr[idx];arr[idx]=val;while(idx<=n)tree[idx]+=delta,idx+=idx&-idx;}ll all(int idx){ll sum=0;while(idx>0)sum+=tree[idx],idx-=idx&-idx;return sum;}ll query(int a,int b){return all(b)-all(a-1);}};int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n,q;cin>>n>>q;bit b(n);for(int i=1;i<=n;++i){ll x;cin>>x;b.arr[i]=x;b.add(i,x);}while(q--){int s;cin>>s;if(s==1){int k;ll u;cin>>k>>u;b.update(k,u);}else{int l,r;cin>>l>>r;cout<<b.query(l,r)<<'\n';}}return 0;
}