算法系列：树状数组

树状数组是一个查询和修改复杂度都为 $log(n)$ 的数据结构。用二进制的位数代表数组的索引值，主要用于数组的单点修改和区间求和。

更新过程是每次加了个二进制的低位1$ (101+1 ->110, 110 + 10 -> 1000, 1000 + 1000 -> 10000)$

查询过程每次就是去掉了二进制中的低位1$ (1111 - 1 -> 1110, 1110 - 10 -> 1100, 1100 - 100 -> 1000)$

所以需要一个取出x的最低位1的函数$lowbit(x)$。

int lowbit(x){return x&(-x);}

具体更新和查询的过程，可以参考后面例题的代码，这里就不放了哈。

1. POJ 3067 Japan

题意：日本计划在东边的城市和西边的城市中建路，东边的点从 $1…..n$，西边的点从 $1…..m$, 求这些点连起来后有多少交叉。

这个题其实是求逆序对的个数，本质上还是考察树状数组的应用。

#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int tr[N];
int n, m, k, res;
struct node
{
    int l, r;
}num[N];
bool cmp(node a, node b) {
    if(a.l == b.l) return a.r < b.r;
    return a.l < b.l;
}
int lowbit(int x) {
    return x & (-x);
}
void update(int x, int a) {
    for(int i = x; i <= m; i += lowbit(i)) {
        tr[i] += a;
    }
}
int getsum(int x) {
    int sum = 0;
    for(int i = x; i; i -= lowbit(i)) {
        sum += tr[i];
    }
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    int T;
    cin >> T;
    while(T--) {
        res = 0;
        cin >> n >> m >> k;
        for(int i = 0; i < k; i++) {
            cin >> num[i].l >> num[i].r;
        }
        // 先根据左边的坐标进行排序
        sort(num, num + k, cmp);
        for(int i = 0; i < k; i++) {
            // 算出当前线跟之前线的焦点个数，不断累加
            res += getsum(m) - getsum(num[i].r);
            // 在该点的右边坐标+1
            update(num[i].r, 1);
        }
        cout << res << endl;
    }
    return 0;
}

2.PAT A1057 Stack

题目链接

这个题的关键问题是求一些给定数的中位数，由于数据范围较大，直接暴力的话，肯定会超时，所以我们才有树状数组，根据查询前缀和的方式 + 二分查找来优化此题。

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int N = 100005;
int tree[N];
int n;
stack<int> s;
int lowbit(int x) {
    return x & (-x);
}
void update(int x, int d) {
    for(int i = x; i < N; i += lowbit(i)) {
        tree[i] += d;
    }
}
int getsum(int x) {
    int sum = 0;
    for(int i = x; i; i -= lowbit(i)) {
        sum += tree[i];
    }
    return sum;
}
int PeekMedian() {
    int len = s.size();
    int target = len % 2 == 0 ? len / 2 : (len + 1) / 2;
    int l = 1, r = N;
    // 整数二分查找模版
    while(l < r) {
        int mid = l + r >> 1;
        if(getsum(mid) >= target)  r = mid;
        else l = mid + 1;
    }
    return l;
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) {
        string str;
        cin >> str;
        if(str == "Push") {
            int t;
            cin >> t;
            s.push(t);
            // 更新该位置的值为1
            update(t, 1);
        }                           
        else if(str == "Pop") {
            if(s.size() == 0) {
                cout << "Invalid" << endl;
            } else {
                cout << s.top() << endl;
                // 恢复该位置的值为0
                update(s.top(), -1);
                s.pop();
            }
        }
        else if(str == "PeekMedian") {
            if(s.size() == 0) {
                cout << "Invalid" << endl;
            } else {
                cout << PeekMedian() << endl;
            }
        }
    }   
    return 0;
}