[ Persistent Binary Index Tree ] 持久化BIT

(二分索引樹)BIT是一種容易實現的資料結構，但在持久化的應用上是非常困難的，但我們可以犧牲些許的複雜度來簡化其實現方式

一般區間和的BIT長這樣:

	int n;
	int tree[100005];
	#define lowbit(x) x&(-x)
	inline void modify(int x,int d){
	for(;x<=n;x+=lowbit(x))tree[x]+=d;
	}
	inline int query(int x){
	int ans=0;
	for(;x;x-=lowbit(x))ans+=tree[x];
	return ans;
	}

view raw BIT.cpp hosted with ❤ by GitHub

這是持久化的版本(也可以用pair來實作):

	#include<vector>
	#include<algorithm>
	#define lowbit(x) x&(-x)
	struct P{
	int data,id;
	P(int d=0,int i=0):data(d),id(i){}
	inline friend bool operator<(const P &a,const P &b){
	return a.id<b.id;
	}
	};
	int n,now;
	std::vector<P >tree[100005];
	inline void init(){
	now=0;
	for(int i=1;i<=n;++i)tree[i].clear(),tree[i].push_back(P());
	}
	inline void modify(int x,int d){
	for(;x<=n;x+=lowbit(x))tree[x].push_back(P(tree[x].back().data+d,now));
	++now;
	}
	inline int query(int x,int id){/*查詢第id次操作的區間和，id從0開始計算*/
	int ans=0;
	std::vector<P >::iterator a;
	for(;x;x-=lowbit(x)){
	a=std::upper_bound(tree[x].begin(),tree[x].end(),P(0,id))-1;
	ans+=a->data;
	}
	return ans;
	}

view raw Persistent BIT.cpp hosted with ❤ by GitHub

可以知道其更新的複雜度為$\ord{logN}$，查詢複雜度為$\ord{logN*logQ}$，Q是查詢次數