P3374 【模板】树状数组 1
题目大意
给定一个长度为 n的数列，需要支持两种操作：
- 单点修改：将第 x 个数加上 k。
- 区间查询：输出区间 [x,y]内所有数的和。
数据范围： 1≤n,m≤5×1e5，数值可能为负，但区间和在 [−2的31次方,2的31次方][−2的31次方,2的31次方] 内。
分析
如果直接使用普通数组，单点修改是 O(1)，但区间查询需要遍历区间，每次 O(n)，在 mm很大时不可行。
如果使用前缀和数组，区间查询是 O(1)，但单点修改需要更新后续所有前缀和，每次 O(n)，同样不可行。
需要一种能平衡修改和查询的数据结构，使得两者都能在 O(logn)内完成。树状数组（Fenwick Tree） 正是为此而生，它利用二进制拆分思想，用较少的额外空间实现了高效的动态前缀和查询与单点更新。
一般思路
当我们遇到需要频繁进行单点更新和区间求和的问题时，首先想到的优化方向是降低查询或更新的复杂度。朴素做法：
数组存原值：更新 O(1)，求和 O(n)。
前缀和数组：更新 O(n)，求和 O(1)。
我们希望两者都做到 O(logn)，树状数组通过维护部分区间和来达成目标：
每个位置 i维护的是原数组中以 i 结尾的某段区间和，这段区间的长度由 lowbit(i) 决定。
更新时，需要更新所有包含该位置的区间（即不断加上 lowbit 跳到下一个包含它的区间）。
查询前缀和时，不断减去 lowbit 累加对应区间的和。
这样，单点修改和前缀和查询都是 O(logn)，区间和则通过两个前缀和相减得到。
Solution
标签： 数据结构，树状数组
树状数组原理
树状数组的核心是 lowbit 运算：lowbit(x) = x & (-x)，它得到 xx 二进制下最低位的 1 所代表的数值。
树状数组 tree[i] 存储的是原数组从下标 i - lowbit(i) + 1 到 i 的和。
因此，要查询前缀和 sum(i)，只需累加 tree[i]、tree[i - lowbit(i)]、…… 直到 0。
要修改位置 pos，则需要更新所有包含 pos 的区间，即 tree[pos]、tree[pos + lowbit(pos)]、…… 直到 n。
代码实现说明
vector
lowbit(x)：返回 x & -x。
add(pos, num)：将位置 pos 增加 num，循环更新 tree[pos] 并 pos += lowbit(pos)。
sum(pos)：返回前缀和 [1, pos]，循环累加 tree[pos] 并 pos -= lowbit(pos)。
主函数 solve 中：
读入 n, m 和初始数组，通过 add(i, a) 构建树状数组。
处理每个操作：
若 op == 1：单点修改，调用 add(a, b)。
若 op == 2：区间查询，输出 sum(b) - sum(a-1)。
时间复杂度
每次 add 和 sum 操作都是 O(logn)。
总复杂度 O((n+m)logn，在 n,m≤5×1e5 时完全可行。
下面是代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;ll n,m;
vector<ll> aa,tree;ll lowbit(ll x){return x & (-x);
}
void add(ll pos, ll num){while(pos <= n){tree[pos] += num;pos += lowbit(pos);}
}
ll sum(ll pos){ll res = 0;while(pos >= 1){res += tree[pos];pos -= lowbit(pos);}return res;
}void solve(){cin >> n >> m;aa.push_back(0);tree.resize(n + 1,0);for(ll i = 1; i <= n; i++){ll a; cin >> a;aa.push_back(a);add(i,a);}for(ll i = 1; i <= m; i++){ll op,a,b; cin >> op >> a >> b;if(op == 1){add(a,b);}else{cout<<sum(b) - sum(a - 1)<<endl;}}
}int main(){ios::sync_with_stdio(0); cin.tie(0);ll t = 1; //cin >> t;while(t--){solve();}return 0;
}