代码模板-树状数组

树状数组基于二进制拆分，用 $c[i]$ 维护以 $i$ 结尾、长度为 $lowbit(i)$ 的区间 $[i-lowbit(i)+1,,i]$ 的和。树深 $O(\log n)$，修改与查询均为 $O(\log n)$。

1	#define lowbit(x) ((x)&(-(x)))

单点修改 + 区间查询（维护前缀和）

const int N = 5e5 + 5;
int c[N], n;

void add(int id, int x) {        // 单点修改：a[id] += x
    for (int i = id; i <= n; i += lowbit(i)) c[i] += x;
}

int query(int id) {              // 前缀查询：sum(a[1..id])
    int ans = 0;
    for (int i = id; i > 0; i -= lowbit(i)) ans += c[i];
    return ans;
}

int query(int l, int r) {        // 区间查询：sum(a[l..r])
    return query(r) - query(l - 1);
}

提示

把树状数组当桶用（权值树状数组），即可统计比某数小的个数，用于求逆序对等。
值域大时注意要先离散化。

逆序对

const int N = 5e5 + 5;
int n, a[N], b[N], m, c[N];
long long ans;

#define lowbit(x) ((x) & (-(x)))

void add(int id, int x) {
    for (int i = id; i <= n; i += lowbit(i)) c[i] += x;
}

int sum(int id) {
    int s = 0;
    for (int i = id; i; i -= lowbit(i)) s += c[i];
    return s;
}

// 离散化：返回 b[] 中 x 的排名（1-based）
int getRank(int x) {
    return lower_bound(b + 1, b + 1 + n, x) - b;
}

signed main() {
    ios::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        b[i] = a[i];
    }
    // 离散化
    sort(b + 1, b + 1 + n);
    m = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; ++i) a[i] = getRank(a[i]);

    // 从右往左，每来一个数查询已出现的比它小的个数
    for (int i = n; i; --i) {
        ans += sum(a[i] - 1);  // 严格小于 a[i] 的个数
        add(a[i], 1);           // 标记 a[i] 已出现
    }
    cout << ans << '\n';
}

区间修改 + 单点查询（差分）

维护差分数组 $b[i]=a[i]-a[i-1]$，则 $a[id]=\sum_{j=1}^{id} b[j]$。

int c[N], n;

void add(int id, int x) {
    for (int i = id; i <= n; i += lowbit(i)) c[i] += x;
}

void add(int l, int r, int x) {  // 区间修改：a[l..r] += x
    add(l, x), add(r + 1, -x);
}

int query(int id) {              // 单点查询：a[id]
    int ans = 0;
    for (int i = id; i > 0; i -= lowbit(i)) ans += c[i];
    return ans;
}

区间修改 + 区间查询（差分 + 维护 i·b[i]）

由 $\sum_{i=1}^x a[i] = (x+1)\sum_{i=1}^x b[i] - \sum_{i=1}^x i\cdot b[i]$，用两个树状数组分别维护 $b[i]$ 与 $i\cdot b[i]$。

#define lowbit(x) ((x)&(-(x)))

const int N = 1e6 + 5;
int c1[N], c2[N], n;   // c1 维护 b[i]，c2 维护 i*b[i]

void add(int id, int x) {
    for (int i = id; i <= n; i += lowbit(i)) {
        c1[i] += x;
        c2[i] += id * x;
    }
}
void add(int l, int r, int x) {           // 区间修改：a[l..r] += x
    add(l, x), add(r + 1, -x);
}
int query1(int id) {                       // S1 = sum(b[1..id])
    int s = 0;
    for (int i = id; i; i -= lowbit(i)) s += c1[i];
    return s;
}
int query2(int id) {                       // S2 = sum(i*b[i], i=1..id)
    int s = 0;
    for (int i = id; i; i -= lowbit(i)) s += c2[i];
    return s;
}
int query(int id) {                        // 前缀和 sum(a[1..id])
    return (id + 1) * query1(id) - query2(id);
}
int query(int l, int r) {                  // 区间查询 sum(a[l..r])
    return query(r) - query(l - 1);
}

相关笔记：【数据结构】树状数组学习笔记