天天看點
傳回

st表、樹狀數組、線段樹和主席樹樹狀數組 :線段樹push_down主席樹參考例題

樹狀數組 :

單點修改 （+ - * /）

區間修改（ + - 最值）其中+ -要利用查分數組來實作

單點查詢 傳統方法

區間查詢 最值得話就循規蹈矩的進行查找

但是如果使用區間修改過（查分數組）後再進行區間查詢，則要進行計算一下

∑ni = 1A[i] = ∑ni = 1 ∑ij = 1D[j];

	則A[1]+A[2]+...+A[n]

	= (D[1]) + (D[1]+D[2]) + ... + (D[1]+D[2]+...+D[n]) 
 
	= n*D[1] + (n-1)*D[2] +... +D[n]
是以說，樹狀數組對于去區間的修改很難辦到，可以用數組維護差分數組，但是這樣的話對區間的查詢就很難辦到了，是以，樹狀數組适合維護單點修改，單點查詢和區間查詢，對于區間的修改我們使用樹狀數組進行維護即可。

單點修改

void update(int pos,int val )
{
	for(int i=pos;i<=maxn;i+=lowbit(i))
	{
		t[i]+=val;//如果是區間最大值則要修改一下 
		
	}		
}

區間查詢

void query(int l,int r)
{
	int sum=0;
	
	while(l<=r)
	{
		for(;r-lowbit(r)>=l;r-=lowbit(r))
		{
			sum+=tree[r];
		}
		sum+=tree[r];
		r--;		
	}	 	
}

區間修改 單點查詢 d數組是查分數組 第I項的值則是前i項的d[i]和

void  update(int l,int r,int val)
{	
	d[l]+=val;
	d[r+1]-=val;	
}

ST表求區間最大值

st表、樹狀數組、線段樹和主席樹樹狀數組 :線段樹push_down主席樹參考例題
st表、樹狀數組、線段樹和主席樹樹狀數組 :線段樹push_down主席樹參考例題
for(int i=1;i<=n;i++)
 st[i][0]=a[i];
 for(int j=0;(1<<j)<=n;j++)
 {
 	for(int i=1;i+(1<<j)-1<=n;i++)
 	{
 		st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
 		
 	}
 } 
 void query(int l,int r)
 {
 	int k=log2(r-l+1);
 	return max(f[l][k],f[r-(1<<k)+1][k]);
 	
 }

線段樹

線段樹就是用來維護一個區間而建立的一棵樹，線段樹中每一個節點維護的都是一個區間

如果父節點維護的區間是[ l , r ] ，那麼兩個子節點s維護的區間分别為[ l,( l+r )/2 ] 和 [ ( l+r )/2+1, r ]。

st表、樹狀數組、線段樹和主席樹樹狀數組 :線段樹push_down主席樹參考例題
st表、樹狀數組、線段樹和主席樹樹狀數組 :線段樹push_down主席樹參考例題

push_down

st表、樹狀數組、線段樹和主席樹樹狀數組 :線段樹push_down主席樹參考例題

這裡給一個線段樹維護一段區間内的和的代碼

const int maxn=1e5+10;
long long a[maxn],lazy[maxn<<2];
long long tree[maxn<<2];
void push_up(int rt)
{
	tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
void push_down(int rt,int l,int r)
{
	if(lazy[rt])
	{
		lazy[rt<<1]+=lazy[rt];
		lazy[rt<<1|1]+=lazy[rt];
		
		int m=(l+r)>>1;
		tree[rt<<1]+=(m-l+1)*lazy[rt];
		tree[rt<<1|1]+=(r-m)*lazy[rt];
		lazy[rt]=0;
	}		
}
void build(int rt,int l,int r)
{
	if(l==r)
	{
		tree[rt]=a[l];
		return ;
	}
	
	int m=(l+r)>>1;
	build(rt<<1,l,m);
	build(rt<<1|1,m+1,r);
	push_up(rt);
	
}

void update(int rt,int l,int r,int ll,int rr,int val)
{
//	if(l==r)
//	{
//		
//		tree[rt]+=val;
//		return ;
//	}
	if(l>=ll&&rr>=r)
	{
		lazy[rt]+=val;
		tree[rt]+=(r-l+1)*val;
		return;
	}
	
	push_down(rt,l,r);
	
	int m=(r+l)>>1;
	if(m>=ll) update(rt<<1,l,m,ll,rr,val);
	if(m+1<=rr) update(rt<<1|1,m+1,r,ll,rr,val);
	
	push_up(rt);
}

long long query(int rt,int l,int r,int ll,int rr)
{
	long long res=0;
	
//	if(l==r)
//	{
//		return tree[rt];		
//	}
	if(l>=ll&&r<=rr)
	{
		return tree[rt];
	}
	
	push_down(rt,l,r);
	int m=(l+r)>>1;
	if(m>=ll) res+=query(rt<<1,l,m,ll,rr);
	if(m+1<=rr) res+=query(rt<<1|1,m+1,r,ll,rr);
	
	return res;
}

主席樹

主席樹就是可持久化線段樹，線段樹經過若幹次修改後，仍然能找到原來某次修改前的線段樹的資訊的一種資料結構

主席樹空間一般開40倍左右

代碼中我注釋的部分是建樹是先整個建成一棵樹，等到以後有更新操作了在重建立另一棵樹

const int maxn=1e5;
int root[maxn];//這裡是用來儲存第i次更新後根節點的下标的 
struct node{
	int l,r; //這裡l和r記錄的是此節點的左孩子和右孩子下标，不是它維護的區間範圍 
	int val; //維護的值 
	int lazy;
	node()
	{
		val=0;
		lazy=0;
	}
}tree[maxn*40];
 
void init()
{
	fill(root,root+maxn,0);
}

void push(int rt)
{
	tree[rt].val=tree[tree[rt].l].val+tree[tree[rt].r].val;	
}

void push_down(int rt,int l,int r)
{
	if(tree[rt].lazy)
	{
		tree[tree[rt].l].lazy+=tree[rt].lazy;
		tree[tree[rt].r].lazy+=tree[rt].lazy;
		
		int m=(l+r)>>1;
		tree[tree[rt].l].val+=(m-l+1)*tree[rt].lazy;
		tree[tree[rt].r].val+=(r-m)*tree[rt].lazy;
		tree[rt].lazy=0;	
	}	
}

//這裡的x和y分别表示這一個根節點個它前一個根節點的下标 
/*void build(int &x,int y,int l,int r,int p)
{
	x=++cnt;
	tree[cnt]=tree[y];
	
	
	if(l==r)
	{
		tree[cnt].val=a[l];
		return ;
	}
	
	int m=(l+r)>>1;
	if(p<=m) build(tree[cnt].l,tree[y].l,l,m,p);
	if(p>=m+1)	 build(tree[cnt].r,tree[y].r,m+1,r,p);	
	
	push_up(cnt);
}*/

void build(int &x,int l,int r)
{
	x=++cnt;
	if(l==r)
	{
		tree[x].val=a[l];
		return ;
	}
	
	int m=(r+l)>>1;
	build(tree[x].l,l,m);
	build(tree[x].r,m+1,r);
	
	push_up(x);	
}

void update(int &x,int y,int l,int r,int ll,int rr,int v)
{
	x=++cnt;
	tree[x]=tree[y];
	
	if(l<=ll&&rr>=r)
	{
		tree[x].lazy+=v;
		tree[x].val+=(r-l+1)*v;
		return;
	}
	
	push_down(rt,l,r);
	
	int m=(l+r)>>1;
	if(m>=ll) update(tree[x].l,tree[y].r,l,m,ll,rr,v);
	if(m+1<=rr) update(tree[x].r,tree[y].r,m+1,r,ll,rr,v);
	
	push_up(rt);	
}

int query(int x,int l,int r,int ll,int rr)
{
	if(l>=ll&&rr>=r)
	{
		return tree[x].val;		
	}
	
	push_down(x,l,r);
	
	int res=0;
	int m=(r+l)>>1;
	if(ll<=m) res+=query(tree[x].l,l,m,ll,rr);
	if(rr>=m+1) res+=query(tree[x].r,m+1,r,ll,rr);
	
	return res;	
}

這個代碼是在建樹的時候每加入一個節點建立一棵樹，這樣友善對一個區間内的節點進行操作

const int maxn=1e5;
int root[maxn];//這裡是用來儲存第i次更新後根節點的下标的 
struct node{
	int l,r; //這裡l和r記錄的是此節點的左孩子和右孩子下标，不是它維護的區間範圍 
	int val; //維護的值 
	int lazy;
	node()
	{
		val=0;
		lazy=0;
	}
}tree[maxn*40];
 
void init()
{
	fill(root,root+maxn,0);
}

void push(int rt)
{
	tree[rt].val=tree[tree[rt].l].val+tree[tree[rt].r].val;	
}

void push_down(int rt,int l,int r)
{
	if(tree[rt].lazy)
	{
		tree[tree[rt].l].lazy+=tree[rt].lazy;
		tree[tree[rt].r].lazy+=tree[rt].lazy;
		
		int m=(l+r)>>1;
		tree[tree[rt].l].val+=(m-l+1)*tree[rt].lazy;
		tree[tree[rt].r].val+=(r-m)*tree[rt].lazy;
		tree[rt].lazy=0;	
	}	
}

//這裡的x和y分别表示這一個根節點個它前一個根節點的下标 
void build(int &x,int y,int l,int r,int p)
{
	x=++cnt;
	tree[cnt]=tree[y];
	
	
	if(l==r)
	{
		tree[cnt].val=a[l];
		return ;
	}
	
	int m=(l+r)>>1;
	if(p<=m) build(tree[cnt].l,tree[y].l,l,m,p);
	if(p>=m+1)	 build(tree[cnt].r,tree[y].r,m+1,r,p);	
	
	push_up(cnt);
}

void update(int &x,int y,int l,int r,int ll,int rr,int v)
{
	x=++cnt;
	tree[x]=tree[y];
	
	if(l<=ll&&rr>=r)
	{
		tree[x].lazy+=v;
		tree[x].val+=(r-l+1)*v;
		return;
	}
	
	push_down(rt,l,r);
	
	int m=(l+r)>>1;
	if(m>=ll) update(tree[x].l,tree[y].r,l,m,ll,rr,v);
	if(m+1<=rr) update(tree[x].r,tree[y].r,m+1,r,ll,rr,v);
	
	push_up(rt);	
}

int query(int x,int l,int r,int ll,int rr)
{
	if(l>=ll&&rr>=r)
	{
		return tree[x].val;		
	}
	
	push_down(x,l,r);
	
	int res=0;
	int m=(r+l)>>1;
	if(ll<=m) res+=query(tree[x].l,l,m,ll,rr);
	if(rr>=m+1) res+=query(tree[x].r,m+1,r,ll,rr);
	
	return res;	
}

參考例題

1.求第k小 

#include<cstdio>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 1e5+5;
int cnt,root[maxn],a[maxn];
//root[i] 第i課線段樹根節點的位置 
//cnt 用作開辟新的樹節點。
struct node{
	int l,r;//左右兒子結點編号，因為不滿足2*rt規律 
	int sum;//代表(l,r)區間上和是多少 
}T[maxn*40];
vector<int> v;
int getid(int x){
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
/** update函數介紹
l,r 代表線段樹遞歸的區間，x代表前一棵樹的節點位置，y是後面的節點位置。
在遞歸的過程中，将需要修改的樹節點複制到新開辟節點，改變自己的sum，
也就是自加1，順便改變上一個的孩子節點
是以傳參是引用傳參；//線段樹區間統計，sum代表在這個區間數的個數。
*/
//update(1,n,root[i],root[i-1],getid(a[i]));
void update(int l,int r,int &x,int y,int p){
	T[++cnt] = T[y];//左右son和sum都先連接配接 
	T[cnt].sum++;
	x = cnt;
	if(l==r) return ;
	int m = (l+r)>>1;
	if(m>=p) update(l,m,T[x].l,T[y].l,p);
	else update(m+1,r,T[x].r,T[y].r,p);
}
/**  query函數介紹
因為是查找第K小，是以在查找時候隻需要看左邊孩子節點，
兩棵線段樹sum做差，便得到這個區間的值
比如 root[R]-root[L-1] ,則代表區間 [L,R] 的數的統計
是以 S=(R線段樹左孩子的sum)-(L-1線段樹左孩子的sum)
 如果 S>=K(第K小)，是以第K小肯定在左兒子節點，
否則，右節點，并且在右邊區間再找剩下的 K-S,即可。
*/
//query(1,n,root[l],root[r],k); 
int query(int l,int r,int x,int y,int k){
	if(l == r) return l;
	int m = (l+r)>>1;
	int sum = T[T[y].l].sum - T[T[x].l].sum;
	if(k<=sum) return query(l,m,T[x].l,T[y].l,k);
	else return query(m+1,r,T[x].r,T[y].r,k-sum);
}
 
int main(){
	int n,m,x,y,k;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		v.push_back(a[i]);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());//去重
 
	for(int i=1;i<=n;i++) 
		update(1,n,root[i],root[i-1],getid(a[i]));
	for(int i=1;i<=m;i++) {	
		scanf("%d%d%d",&x,&y,&k);	
		printf("%d\n",v[query(1,n,root[x-1],root[y],k)-1]);//why -1
	}	
	return 0;
}

2.題意：

一個長度為n的數組，4種操作 ： （1）C l r d：區間[l,r]中的數都加1，同時目前的時間戳加1 。 （2）Q l r：查詢目前時間戳區間[l,r]中所有數的和 。 （3）H l r t：查詢時間戳t區間[l,r]的和 。 （4）B t：将目前時間戳置為t 。 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
using namespace std;
#define pb push_back 
typedef long long ll;
const int maxn = 100009;

struct node {
    int l,r;
    ll sum,lazy;
}T[maxn*40];
int root[maxn],cur,tot;
ll a[maxn];


void build(int l,int r,int &pos)
{
    pos = tot++;
    T[pos].sum = T[pos].lazy = 0;
            // T[pos].l = l,T[pos].r = r;
    if(l==r)
    {
        T[pos].sum = a[l];
        return;
    }
    int mid = (l+r)>>1;
    build(l,mid,T[pos].l);
    build(mid+1,r,T[pos].r);
    T[pos].sum = T[T[pos].l].sum + T[T[pos].r].sum;
}
void update(int L,int R, int &x, int y , int l, int r, int d)//這裡的x和上面的pos類似
{
    x = tot++;
    T[x] = T[y];
    
    if(l>=L && r<=R)
    {
        T[x].sum += 1ll*(r - l + 1) * d;                    //這裡用目标區間的L，R；因為目标區間每個值都要加上
        T[x].lazy += d;
        return;
    }
    int mid = (l+r)>>1;
    if(L <= mid)
        update(L, R, T[x].l, T[y].l, l, mid, d);
    if(R > mid)                                   
        update(L, R, T[x].r, T[y].r, mid+1,r, d);

    T[x].sum = T[T[x].l].sum + T[T[x].r].sum + 1ll*(r-l+1) * T[x].lazy;
}
ll query(int L,int R,int x,int l,int r)
{
            if(L<=l && R>=r)
            {
                return T[x].sum;
            }
            ll ans = 1ll*T[x].lazy*(min(R,r)-max(L,l) + 1);
            int mid = (l+r)>>1;
            if(R  > mid)
                ans += query(L,R,T[x].r, mid+1, r);
            if(L<=mid)
                ans += query(L,R,T[x].l, l,mid);
            return ans;
}
int main()
{
            int n,m;
            int flag = 0;
            while(~scanf("%d%d", &n, &m))
            {   
                if(flag)puts("");
                flag = 1;
                tot = 0,cur = 0;
                for(int i=1; i<=n; i++)
                {
                    scanf("%lld", &a[i]);
                }
                // root[0] = tot++;
                build(1,n,root[0]); 
                while(m--)
                {
                    char op[20];
                    scanf("%s" , op);
                    if(op[0]=='Q')
                    {
                        int l,r;
                        scanf("%d%d",&l,&r);
                        printf("%lld\n",query(l,r,root[cur],1,n));
                    }
                    else if(op[0]=='C')
                    {
                        int l,r;
                        ll d;
                        scanf("%d%d%lld", &l, &r, &d);
                        cur++;
                        update(l,r,root[cur],root[cur-1], 1, n, d);
                    }
                    else if(op[0]=='H')
                    {   
                        int l,r,t;
                        scanf("%d%d%d",&l,&r,&t);
                        printf("%lld\n",query(l,r,root[t],1,n));
                    }
                    else if(op[0]=='B')
                    {
                        scanf("%d",&cur);
                    }
                }
            }
            return 0;
}
大學期間學習 st表、樹狀數組、線段樹和主席樹
上一篇: java語言實作二叉樹
下一篇: jquery.tools.min.js插件dateinput兩種運用方法

繼續閱讀