树状数组

代码

#define lowbit(x) ((x) & (-x))
ll tree[N];
inline void update(int i, ll x) {
    for (int pos = i; pos < N; pos += lowbit(pos)) tree[pos] += x;
}
inline ll query(int n) {
    ll ans = 0;
    for (int pos = n; pos; pos -= lowbit(pos)) ans += tree[pos];
    return ans;
}
inline ll query(int a, int b) { return query(b) - query(a - 1); }

What

树状数组支持：

• 单点修改：更改数组中一个元素的值
• 区间查询：查询一个区间内所有元素的和

两种操作的时间复杂度均为，是暴力（+）和前缀和（+）的折中。

可以通过引入差分数组的方式完成对区间修改，单点查询的支持。

Why

How

逆序数

（待填）