模板

#include <bits/stdc++.h>
using namespace std;
int n, m, l, r;
int a[100005], c[100005];
int lowbit(int x)
{
    return x & (-x);
}
int ask(int x)//区间[1,x]的前缀和
{
    int ans = 0;
    while(x > 0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
void add(int x, int d)//树状数组添加
{
    while(x <= n){
        c[x] += d;
        x += lowbit(x);
    }
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) add(i, a[i]);
    cin >> m;
    for(int i = 1; i <= m; i++){
        cin >> l >> r;
        cout << ask(r) - ask(l - 1) << "\n";
    }
    return 0;
}

应用：

求逆序对：

#include <bits/stdc++.h>
using namespace std;
int n, m, l, r;
long long ans = 0;
int a[100005], c[100005];
int lowbit(int x)
{
    return x & (-x);
}
int ask(int x)//区间[1,x]的前缀和
{
    int ans = 0;
    while(x > 0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
void add(int x, int d)//树状数组添加
{
    while(x <= n){
        c[x] += d;
        x += lowbit(x);
    }
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = n; i >= 1; i--){
        ans += ask(a[i] - 1);//求出序列后方比a[i]小的数量
        add(a[i], 1);//将数字加入树状数组
    }
    cout << ans;
    return 0;
}

离散化优化：

所谓离散化就是指对序列中的数值按数值大小重新标号，最小值标为 $1$，最大值标为 $n$。

步骤：

①先建立一个备用数组 $t[i]$;

②对数组 $t[i]$ 排序；

③对数组 $t[i]$ 去重；

④将原数值 $a[i]$ 放到 $t[i]$ 中二分查找，得到自己的顺序号，将顺序号更新为自己的新数值。

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], t[i] = a[i];
    sort(t + 1, t + n + 1);//排序
    int len = unique(t + 1, t + n + 1) - t - 1;//去重
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(t + 1, t + len + 1, a[i]) - t;//将原数重新标号
    }
    return 0;
}

用离散化优化：

#include <bits/stdc++.h>
using namespace std;
int n, m, l, r;
long long ans = 0;
int a[100005], c[100005], t[100005];
int lowbit(int x)
{
    return x & (-x);
}
int ask(int x)//区间[1,x]的前缀和
{
    int ans = 0;
    while(x > 0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
void add(int x, int d)//树状数组添加
{
    while(x <= n){
        c[x] += d;
        x += lowbit(x);
    }
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], t[i] = a[i];
    //离散化
    sort(t + 1, t + n + 1);//排序
    int len = unique(t + 1, t + n + 1) - t - 1;//去重
    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(t + 1, t + len + 1, a[i]) - t;//将原数重新标号
    }
    for(int i = n; i >= 1; i--){
        ans += ask(a[i] - 1);//求出序列后方比a[i]小的数量
        add(a[i], 1);//将数字加入树状数组
    }
    cout << ans;
    return 0;
}