树状数组求前缀和

int val[maxn];
void modify(int pos, int delta){
    for(int i=pos; i<=max_pos; i+=(-i)&i) val[i] += delta;
}
int query(int pos){
    int ret = 0;
    for(int i=pos; pos>0; i-=(-i)&i) ret += val[i];
    return ret;
}

树状数组求区间最值

例题洛谷P3865 (opens new window)

ST表的模板题，肯定不能用ST做啦~

注：从代码中可以看出，该方法对在线修改类型有限制（数值只能增加不能减少），但是离线完全没问题

ST表(1.22s，8.51M)，树状数组（1.29s，6.9M），耗时差不多，但内存占用少了

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)

using namespace std;

const int maxn = 1e6 + 100;

int bit[maxn] = {0}, val[maxn];

void update(int x, int pos, int n){
    while(pos <= n){
        bit[pos] = max(bit[pos], x);
        pos += (-pos) & pos;
    }
}

int query(int l, int r){ // 结果包含左/右端点
    int ans = val[r], tmp;
    while(l <= r){ // 如果l可能为0，需要特判
        tmp = r - (r & (-r));
        if(tmp >= l){
            ans = max(ans, bit[r]);
            r = tmp;
        }else{
            ans = max(ans, val[r--]); // 当减去lowbit后小于l时，同原数组对比
        }
    }
    return ans;
}

signed main(){
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) {
        cin >> val[i];
        update(val[i], i, n);
    }
    for(int i=0, l, r; i<m; i++){
        cin >> l >> r;
        cout << query(l, r) << '\n';
    }
}

树状数组处理二位偏序

例题Codeforces 12D

题意：求出满足$\exist i,\ a_x<a_i \&\ b_x<b_i\&\ c_x<c_i$的$x$的个数

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 5e5 + 1000;

struct val {
    int a, b, c, idx;
} vals[maxn], tmp[maxn];

bool cmp1(const val & v1, const val & v2){
    if(v1.a == v2.a) {
        if(v1.b == v2.b) return v1.c < v2.c;
        else return v1.b < v2.b;
    }
    return v1.a < v2.a;
}

int va[maxn]={0};
int greatest;
// 树状数组维护p到greatest中最大的值
int query(int p) {
    int ret = 0;
    for(int i = p; i <= greatest; i += (-i)&i) ret = max(ret, va[i]);
    return ret;
}

void add(int p, int v) {
    for(int i = p; i > 0; i -= (-i)&i) va[i] = max(va[i], v);
}

signed main() {
    int n, ans=0;
    cin >> n;
    vector<int> unq(n + 1);
    for(int i = 1; i <= n; i++) cin >> vals[i].a, vals[i].idx = i;
    for(int i = 1; i <= n; i++) {
        cin >> vals[i].b;
        vals[i].b++;
        unq[i] = vals[i].b;
    }
    for(int i = 1; i <= n; i++) cin >> vals[i].c;
    
    // 对b离散化
    sort(unq.begin(), unq.end());
    unq.resize(unique(unq.begin(), unq.end()) - unq.begin());
    greatest = unq.size() + 3;
    for(int i=1; i<=n; i++) vals[i].b = lower_bound(unq.begin(), unq.end(), vals[i].b) - unq.begin();

    sort(vals + 1, vals + n + 1, cmp1); // 对a排序，问题降为二位偏序问题

    int j = n;
    for(int i=n; i>0; i--){
        if(vals[i].a < vals[j].a){
            for(; j>i; j--) add(vals[j].b, vals[j].c);
        }
        if(query(vals[i].b+1) > vals[i].c) {
            ans++;
        }
    }
    cout << ans << endl;
}

树状数组求第K小

这里我们不使用二分+求前缀和的方法（复杂度$O(log^2n)$）

举个例子：假设$15$为第$4$小的数字，可以拆分成$8+4+2+1$，因此，在查询$15$是否为第$k$大时，我们可以先查询$8$，结果发现$cnt[8]< 4$，接着向查询得$cnt[8+4]<4,cnt[8+4+2]<4,cnt[8+4+2+1]\ge 4$，因此，满足$cnt[x]<4$的最大位置为$x=14$，第$4$的数字为$14+1$

例题 POJ 2985

题意：有$n$只猫，初始第$i$只猫属于第$i$组。对于操作1 u v，要将组$u,v$合并。对于操作2 k，查询第$k$大的组的大小。

注意：在poj上交题，务必使用scanf而非cin

AC代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int maxn = 2e5 + 1000;
int union_set[maxn], cat[maxn];

int lookup(int u){return u==union_set[u]?u:union_set[u]=lookup(union_set[u]);}

int fenwick[maxn], n, m;

void add(int pos, int delta){
    for(int i=pos; i<=n; i+=(-i)&i){
        fenwick[i] += delta;
    }
}

int query(int k){ // 查询第k小
    int pos = 0, cnt = 0;
    for(int i=20; i>=0; i--){
        pos += (1<<i);
        if(pos > n || cnt + fenwick[pos] >= k){
            pos -= (1<<i);
        }else{
            cnt += fenwick[pos];
        }
    }
    return pos + 1;
}

void solve(){
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++) {
        union_set[i] = i;
        cat[i] = 1;
    }
    add(1, n);

    int group_cnt = n;
    for(int i=0, op, a, b; i<m; i++){
        scanf("%d", &op);
        if(op == 0){
            scanf("%d%d", &a, &b);
            a = lookup(a), b = lookup(b);
            if(a != b){
                group_cnt--;
                add(cat[a], -1);
                add(cat[b], -1);
                add(cat[a] = cat[a] + cat[b], 1);
                union_set[b] = a;
            }
        }else{
            scanf("%d", &a);
            // 转化为查询第 group_cnt - a + 1 小
            cout << query(group_cnt - a + 1) << '\n';
        }
    }
}

signed main(){
    solve();
}

参考

https://www.cnblogs.com/wuyiqi/archive/2011/12/25/2301071.html