树状数组

Fenwick Tree 基本模板

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#define lowbit(b) (b)&(-b)
using namespace std;
vector<int> ft;
int n;
void init(int n){
    ft.assign(n+1,0);
}
int rsq(int b){
    int sum = 0;
    while(b){
        sum+=ft[b];
        b-=lowbit(b);
    }
    return sum;
}
int rsq(int a,int b){
    if(a-1) return rsq(b)-rsq(a-1);
    return rsq(b);
}
void update(int k,int v){
    while(k<ft.size()){
        ft[k]+=v;
        k+=lowbit(k);
    }
}

int main(){
    int f[] = {2,4,5,5,6,6,6,7,7,8,9};
    n = 10;//0-based
    init(n);
    for(int i = 0; i < 11; i++)
        update(f[i],1);
    cout << rsq(1,1) << endl;//ft[1]
    cout << rsq(1,2) << endl;//ft[2]
    cout << rsq(1,6) << endl;//ft[6]+ft[4] = 5+2
    cout << rsq(1,10) << endl;//ft[10]+ft[8] = 1+10
    cout << rsq(3,6) << endl;//rsq(1,6)-rsq(1,2)
    update(5,2);
    cout << rsq(1,10) << endl;
    return 0;
}

FT(2D)
POJ1195

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#define lowbit(b) (b)&(-b)
using namespace std;
int ft[1100][1100];
int n,x,y,m,l,b,r,t;
void init(){
    memset(ft,0,sizeof ft);
}
int rsq(int x,int y){
    int sum = 0;
    for(int i = x; i; i -= lowbit(i)){
        for(int j = y; j; j -= lowbit(j)){
            sum+=ft[i][j];
        }
    }
    return sum;
}
int rsq(int l,int b,int r,int t){
    return rsq(r,t)-rsq(r,b-1)-rsq(l-1,t)+rsq(l-1,b-1);
}
void update(int x,int y,int v){
    for(int i = x; i <= n; i += lowbit(i)){
        for(int j = y; j <= n; j += lowbit(j)){
            ft[i][j] += v;
        }
    }
}
int main(){
    int op;
    while(scanf("%d",&op)!=EOF){
        if(op==3) continue;
        else if(op==0){
            scanf("%d",&n);
            init();
        }
        else if(op==1){
            scanf("%d%d%d",&x,&y,&m); x++;y++;
            update(x,y,m);
        }
        else{
            scanf("%d%d%d%d",&l,&b,&r,&t); l++;b++;r++;t++;
            printf("%d\n",rsq(l,b,r,t));
        }
    }
    return 0;
}

求区间的真子集
POJ2481

求第k大
HDU2852(出题人的英语肯定不咋样)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath> 
#define lowbit(b) (b)&(-b)
using namespace std;
const int maxn = 1e2+1e5;
int ft[maxn];
int rsq(int b){
    int sum = 0;
    while(b){
        sum+=ft[b];
        b-=lowbit(b);
    }
    return sum;
}
void update(int k,int v){
    while(k<maxn){
        ft[k]+=v;
        k+=lowbit(k);
    }
}
/*************************find_kth*************************/
int findk(int k){
    int now = 0;
    for(int i = (int)log2(maxn-1); i >= 0; i--){
        now |= (1<<i);
        if(now >= maxn || ft[now] >= k){
            now ^= (1<<i);
        } 
        else k -= ft[now];
    }
    return now+1;
}
/*************************find_kth*************************/
int main(){
    int n,op,x,k;
    ios::sync_with_stdio(false); 
    while(cin>>n){
        memset(ft,0,sizeof ft);
        while(n--){
            cin>>op>>x; x++;
            if(op==0){
                update(x,1); 
            }
            else if(op==1){
                if(rsq(x)-rsq(x-1)==0) printf("No Elment!\n");
                else update(x,-1);
            }
            else{
                cin>>k;
                if(rsq(maxn-1)-rsq(x)<k) printf("Not Find!\n");
                else printf("%d\n",findk(k+rsq(x))-1);
            }
        } 
    }
    return 0;
}

求逆序对(简单)
hihoCoder 1524

#include<cstdio>
#include<cstring>
#define lowbit(b) (b)&(-b)
const int maxn = 100010;
int ft[maxn],a[maxn];
int rsq(int b){
    int sum = 0;
    while(b){
        sum+=ft[b];
        b-=lowbit(b);
    }
    return sum;
}
void update(int k,int v){
    while(k<maxn){
        ft[k]+=v;
        k+=lowbit(k);
    }
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        memset(ft,0,sizeof ft);
        for(int i = 1; i <= n; i++){
            scanf("%d",&a[i]);  a[i]++; 
        }
        int ans = 0;
        for(int i = n; i >= 1; i--){
            ans += rsq(a[i]-1);
            update(a[i],1);
        }
        printf("%d\n",ans);
    }
    return 0;
}

求逆序对(必须离散)
SGU180
思路参考:http://blog.csdn.net/fsahfgsadhsakndas/article/details/52916035
http://blog.csdn.net/elicococoo/article/details/22335973
进阶:CODE[VS] 3286
区间更新查询
很强大完整的笔记:http://blog.csdn.net/lawrence_jang/article/details/8054173
以及文章:树状数组维护区间和的模型及其拓广的简单总结

要实现区间批量更新和单点查询
只需对原数组a[i]进行进行前后差分,设d[i]=a[i]-a[i-1],其中d[1]=a[1],所以单点查询就是a[i]=∑d[1...i];
而关键的区间批量更新比如a[l...r]+=k,只需d[l]+=k,d[r+1]-=k即可,理由就是差分.

∑a[l...r]=∑d[1...l]+∑d[1...l+1]+...+∑d[1...r],

总共加了r-l+1次k,而r后的元素查询必须经过d[r+1],a[i]+k-k=a[i].

在区间更新的前提下实现区间查询
和刚才差不多,注意到d[i]的求和规律,
∑a[1...n]=nd[1]+(n-1)d[2]+...+1d[1]
=∑(n,i=1)(n-i+1)d[i]
=∑(n+1)d[i]-∑id[i]
=(n+1)∑d[i]-∑id[i]
再搞多一棵Fenwick树维护d2[i]=i*d[i]就行了

离散化
SGU180
把绝对的数值转化为相对的数值,空间开销好像没别人的好
用int会WA,93ms

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define lowbit(b) (b)&(-b)
using namespace std;
const int maxn = 1e5;
typedef long long ll;
ll ft[maxn],b[maxn],n;
struct qwert{
    ll val,pos;
    bool operator < (const qwert& that)const{
        return val<that.val;
    }
}a[maxn];
bool cmp(qwert a,qwert b){
    return a.val<b.val;
}
ll rsq(ll b){
    ll sum = 0;
    while(b){
        sum+=ft[b];
        b-=lowbit(b);
    }
    return sum;
}
void update(ll k,ll v){
    while(k<maxn){
        ft[k]+=v;
        k+=lowbit(k);
    }
}
int main(){
    ios::sync_with_stdio(false);
    while(cin>>n){
        memset(ft,0,sizeof ft);
        memset(a,0,sizeof a);
        for(int i = 0; i < n; i++){
            cin>>a[i].val; a[i].pos=i;
        }
        sort(a,a+n,cmp);
        for(int i = 0; i < n; i++){
            b[a[i].pos]=lower_bound(a,a+n,a[i])-a;
            b[a[i].pos]++;
        }
        ll sum = 0;
        for(int i = 0; i < n; i++){
            update(b[i],1);
            sum+=rsq(maxn-1)-rsq(b[i]);
        }
        cout<<sum<<endl;
    }
    return 0;
}

标签: 算法, 学习

添加新评论