下标从一开始。
所有奇数等于本身，偶数/2等于所在层数。
二进制末尾有几个0就在第几层。
每一个树状数组中表示的都是这么一个区间的和，左开右闭。
写成lowbit(x)，返回的就是2^k，k就是末尾有几个0。
这是求和代码
单点修改
这是单点修改，区间查询的代码：
#include<iostream>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;
int n, m, a[N], tr[N];
// O(log2n)
// 树状数组解决：单点修改以及区间查询(常考)，区间修改以及单点查询(配合差分转化为第一种情况)，区间修改以及区间查询(配合差分转化为第一种情况)
// 注意下标一定要从1开始
// 树状树状的所有的奇数和原数组相等(树状数组的第0层)
// c[x]：x的二进制表示最后有k个连续的0，就在第k层
// c[x] 表示的和的范围：(x - 2^k, x]，也就是(x - lowbit(x), x]
// lowbit(x) = x & -x = 2^k
// 所以要求x的前缀和需要递归求解：
// for (int i = 0; i>0; i -= lowbit(i)) res += c[i];
// 修改值后的前缀和：A[x] + v
// for (int i = x; i <= n; i += lowbit(i)) c[i] += v;
// 上述两个循环时间复杂度都是O(log2n)
int lowbit(int x){return x & -x;}
void add(int x, int v)
{
for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}
int query(int x)
{
int res = 0;
for (int i = x; i > 0; i -= lowbit(i)) res += tr[i];
return res;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) add(i, a[i]);
while (m--)
{
int k, x, y; cin >> k >> x >> y;
if (k == 0) cout << query(y) - query(x - 1) << '\n';
else add(x, y);// 在第x位置上加上一个y
}
return 0;
}
这是区间修改，单点查询的代码：
#include<iostream>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<tuple>
#include<set>
#include<bitset>
#include<unordered_map>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 1e5 + 9, mod = 998244353, INF = 0x3f3f3f3f, M = 1, P = 13331;
const double eps = 1e-8;
#define x first
#define y second
typedef pair<int, int> PII;
int T, n, m, k, len, res, e[M], ne[M], h[N], w[M], idx, dist[N], f[N][2], a[N], r, c;
int lowbit(int x) {return x & -x;}
void add(int x, int v) {
for (int i = x; i <= n; i += lowbit(i)) h[i] += v;
}
int query(int x) {
int res = a[x];
for (int i = x; i; i -= lowbit(i)) res += h[i];
return res;
}
// 区间修改，单点查询
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
char op;
while (m--) {
cin >> op;
if (op == 'Q') {
int x; cin >> x;
cout << query(x) << '\n';
}
else {
int l, r, v; cin >> l >> r >> v;
add(l, v), add(r + 1, -v);
}
}
return 0;
}
区间修改，区间查询：
#include<iostream>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<tuple>
#include<set>
#include<bitset>
#include<unordered_map>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 2e5 + 9, mod = 998244353, INF = 0x3f3f3f3f, M = 1, P = 13331;
const double eps = 1e-8;
#define x first
#define y second
typedef pair<int, int> PII;
ll T, n, m, k, len, res, e[M], ne[M], h[N], w[M], idx, dist[N], f[N][2], a[N], r, c;
ll c1[N], c2[N];
ll lowbit(ll x) {return x & -x;}
void add(ll x, ll v) {
for (int i = x; i <= n; i += lowbit(i)) {
c1[i] += v;
c2[i] += x * v;
}
}
ll query(ll x) {
ll res = 0;
for (int i = x; i; i -= lowbit(i)) res += (x + 1) * c1[i] - c2[i];
return res;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
add(i, a[i] - a[i - 1]);
}
char op;
while (m--) {
cin >> op;
if (op == 'Q') {
ll l, r; cin >> l >> r;
cout << query(r) - query(l - 1) << '\n';
}
else {
ll l, r, v; cin >> l >> r >> v;
add(l, v), add(r + 1, -v);
}
}
return 0;
}
