數據結構小結+模板

\[OI中的數據結構\]

\[By\;TYQ\]

線性結構

大部略

單調棧

棧 , 但是push的時候要彈出所有比他小/大的(多用于優化Dp)

單調隊列

隊列 , 同單調棧

樹狀結構

樹狀數組

核心:lowbit(x) = (x) & (-x)

...其實lowbit(x) = 2^x的最低非0位

PION8012初賽中考了...但只涉及正數...

• 為什么lowbit(x) = (x) & (-x)

考慮x>0時-x等于多少:-x在二進制中的意義為x所有位取反后+1 , 那么他的第一個非0位以前的都是0 , &后結果為0 , 在第一個非0位時-x發生進位使哪位為1 , 那么這位為1 , 再以后呢?為0 , 所以&也為0

• 樹狀數組每個節點的值

\(C_{i} = \sum_{j=i}^{j!=0 , j=lowbit(j)} C_{j}\)

• 樹狀數組怎么求和 :

我們為什么要設計前面的\(C_{i}\)為這個奇怪的數?

答案揭曉!為了查詢!當查詢時我們只需要遍歷查詢數的每個lowbit , 將值加上\(C_{x}\)

查詢時間復雜度為\(O(logN)\)

那么這為什么對呢?因為:

.

.

.

畫出這顆樹發現的確是對的QAQ其實是我不會證

關于代碼:

void modify(int x , int y)/*modify a[x] to a[x]+y*/{for(int i=x;i<=n;C[i]+=y,i+=(i)&(-i)) ; }
int query(int x)/*query a[1]+...+a[x]*/{int ret = 0 ;for(int i=x;i;i-=(i)&(-i))ret+=C[i] ; return ret ;}

線段樹

其實一開始你覺得比較難 , 但其實很基礎

線段樹每次將區間分成兩個小區間 , 到底層遞歸 ;

用指針寫偽代碼就是

Query()int sum = 0 ;if(!this->ls) sum+=this->ls.Query()if(!this->rs)sum+=this->rs.Query()return sum ;//什么?你問我為什么要寫指針?代碼短!

但是你代碼肯定不能這么寫...線段樹維護的不只和 , 需要zici區間查詢 :

關于區間查詢

Query(i,j,ni,nj,p)if(i<=ni && j<=nj) return Value[p] ;int m = (s + t) >> 2, sum = 0;if (l <= m) sum += Query(l, r, s, m, p * 2);if (r > m) sum += Query(l, r, m + 1, t, p * 2 + 1);return sum;

pushdown

pushdown(p,m,s,t)d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m),b[p * 2] += b[p], b[p * 2 + 1] += b[p];

區間修改:

每次執行單點修改并給節點打上LazyTag , 需要時下放

板子

#include<iostream>
#include<cstdio>
#define ll      long long
#define MAXN 100000
int p , arr[MAXN+5];
using namespace std ;
struct node{ll v,mul,add;
}tr[4*MAXN+5];
void build(int root,int l,int r){tr[root].mul=1,tr[root].add=0;if(l==r) tr[root].v=arr[l];else {int m=(l+r)/2; build(root*2,l,m) ; build(root*2+1,m+1,r) ;tr[root].v=tr[root*2].v+tr[root*2+1].v ;}tr[root].v%=p ;
}
void pushdown(int root,int l,int r){int mid=(l+r)/2 ;tr[root*2].v=(tr[root*2].v*tr[root].mul+tr[root].add*(mid-l+1))%p,tr[root*2+1].v=(tr[root*2+1].v*tr[root].mul+tr[root].add*(r-mid))%p,tr[root*2].mul=(tr[root*2].mul*tr[root].mul)%p,tr[root*2+1].mul=(tr[root*2+1].mul*tr[root].mul)%p,tr[root*2].add=(tr[root*2].add*tr[root].mul+tr[root].add)%p,tr[root*2+1].add=(tr[root*2+1].add*tr[root].mul+tr[root].add)%p,tr[root].mul=1,tr[root].add=0;
}
void U_M(int root,int il,int ir,int l,int r,ll k){if(r<il||ir<l) return ;if(l<=il&&ir<=r) {tr[root].v=(tr[root].v*k)%p,tr[root].mul=(tr[root].mul*k)%p,tr[root].add=(tr[root].add*k)%p; return ;}pushdown(root,il,ir) ;int mid=(il+ir)/2 ;U_M(root*2,il,mid,l,r,k) ;U_M(root*2+1,mid+1,ir,l,r,k) ;tr[root].v=(tr[root*2].v+tr[root*2+1].v)%p ;return ;
}
void U_A(int root,int il,int ir,int l,int r,ll k){if(r<il||ir<l) return ;if(l<=il&&ir<=r) {tr[root].add=(tr[root].add+k)%p,tr[root].v=(tr[root].v+k*(ir-il+1))%p; return ;}pushdown(root,il,ir) ;int mid=(il+ir)/2 ;U_A(root*2,il,mid,l,r,k) ;U_A(root*2+1,mid+1,ir,l,r,k) ;tr[root].v=(tr[root*2].v+tr[root*2+1].v)%p ;return ;
}
ll query(int root,int il,int ir,int l,int r){if(r<il||ir<l) return 0;if(l<=il&&ir<=r) {return tr[root].v;}pushdown(root,il,ir) ;int mid=(il+ir)/2 ;return (query(root*2,il,mid,l,r)+query(root*2+1,mid+1,ir,l,r))%p;
}
int main(){int n,m ;scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=n;++i) scanf("%d",&arr[i]) ; build(1,1,n) ;//for(int i=1;i<=n;++i) cout<<tr[i].v<<" " ; cout<<endl ;while(m--){int x,y,z; ll k;scanf("%d",&x) ;if(x==1)scanf("%d%d%lld",&y,&z,&k) , U_M(1,1,n,y,z,k) ;else if(x==2)scanf("%d%d%lld",&y,&z,&k) , U_A(1,1,n,y,z,k) ;else scanf("%d%d",&y,&z),printf("%lld\n",query(1,1,n,y,z)) ;//for(int i=1;i<=n;++i) cout<<tr[i].v<<" " ; cout<<endl ;}return 0 ;
}

可持久化

見可持久化數據結構