0x40「數(shù)據(jù)結(jié)構(gòu)進(jìn)階」例題
幾點(diǎn)總結(jié)
1 數(shù)據(jù)結(jié)構(gòu)有兩個用處：組織特定類型的數(shù)據(jù)方便調(diào)用猎醇、高效的實(shí)現(xiàn)數(shù)據(jù)的增刪改查穴墅。換句話說秽之，這兩個用處指向了思考數(shù)據(jù)結(jié)構(gòu)問題時的邏輯過程成肘，即先想到樸素算法（可能是模擬亿遂，貪心浓若，復(fù)雜度較高的DP方程等等），然后我們往往時因?yàn)閿?shù)據(jù)范圍的限制而使用數(shù)據(jù)結(jié)構(gòu)蛇数。也就是說挪钓，數(shù)據(jù)結(jié)構(gòu)本質(zhì)上是一種對算法實(shí)現(xiàn)過程的優(yōu)化惦费。
2 數(shù)據(jù)結(jié)構(gòu)問題中耸彪，很多數(shù)據(jù)結(jié)構(gòu)維護(hù)的信息有相似處，這時需要根據(jù)情況選取特定的數(shù)據(jù)結(jié)構(gòu)丘逸，同時充分考慮代碼量浦徊，實(shí)現(xiàn)難度馏予，算法常數(shù)等因素盔性，最終找到最合適的數(shù)據(jù)結(jié)構(gòu)悉尾。
3 所有樹形數(shù)據(jù)結(jié)構(gòu)還有一個明顯的特征：擅于且僅擅于維護(hù)符合“區(qū)間加法”的信息务漩。具體地說，就是兩個小區(qū)間的最值再取最值可以得到一個大區(qū)間的最值它褪，兩個小區(qū)間的和再求和可以得到一個大區(qū)間的和饵骨。然而，若維護(hù)信息不滿足“區(qū)間加法”茫打，樹形數(shù)據(jù)結(jié)構(gòu)就會在時間復(fù)雜度上產(chǎn)生退化居触。例如妖混，已知兩個小區(qū)間的眾數(shù)，難以在的時間內(nèi)完成合并兩個小區(qū)間得到大區(qū)間眾數(shù)的過程轮洋。
并查集
當(dāng)問題滿足關(guān)系具有傳遞性和無向性時制市，并查集時維護(hù)關(guān)系的一個有用工具。（PS：若是關(guān)系具有傳遞性和有向性弊予，這時可以思考圖論建模和有向圖強(qiáng)連通分量的tarjan算法以及k-sat問題）
并查集的實(shí)現(xiàn)非常簡單祥楣，且屬于基礎(chǔ)內(nèi)容，這里不再贅述汉柒。不過值得一提的是误褪，并查集合并過程中優(yōu)化時間復(fù)雜度的思想非常重要，很多復(fù)雜的問題都會用到碾褂。例如兽间，我們可以通過并查集的路徑壓縮特性過濾很多無用信息。也可以將”按秩合并”推廣到啟發(fā)式合并（啟發(fā)式合并指：將大的結(jié)構(gòu)和小的結(jié)構(gòu)合并時正塌，將小的結(jié)構(gòu)向大的結(jié)構(gòu)合并嘀略，同時只增加小的結(jié)構(gòu)的查詢費(fèi)用）
同時使用路徑壓縮和按秩合并優(yōu)化的并查集的單次查詢/合并時間復(fù)雜度趨近反阿克曼函數(shù)（近似為常數(shù)），但我們遇到的問題中乓诽，往往只要其中的一種合并方式即可帜羊。
首先給出路徑壓縮優(yōu)化的并查集代碼，單次查詢/合并時間復(fù)雜度：
int fa[SIZE];
for (int i = 0; i <= n; i++) fa[i] = i;
int get(int x) {
if (x == fa[x]) return x;
return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
fa[get(x)] = get(y);
}
例題
4101 銀河英雄傳說
顯然问裕，最后的戰(zhàn)艦排列是一條條“鏈”逮壁，即一種特殊形態(tài)的樹，我們可以用并查集維護(hù)粮宛。
本題中需要我們維護(hù)一些并查集森林中的特殊信息窥淆。具體地說，我們需要對于每個元素x巍杈，它到所在樹的樹根的距離d[x]和以它為根的子樹的size[x]（注意：由于路徑壓縮的存在忧饭，我們得到的并查集森林中并不是一條條的“鏈”），這樣若x元素和y元素在同一列筷畦，那么他們之間的距離（不包括x和y）就是|d[y]-d[x]|-1
d[x]和size[x]的具體計(jì)算過程代碼如下
int get(int x) {
if (x == fa[x]) return x;
int root = get(fa[x]);
d[x] += d[fa[x]];
return fa[x] = root;
}
void merge(int x, int y) {
x = get(x), y = get(y);
fa[x] = y, d[x] = size[y];
size[y] += size[x];
}
如果我們面對的問題中需要維護(hù)明顯對立的兩/三/更多的集合词裤，同時“傳遞關(guān)系”可以相互導(dǎo)出時，那么我們會使用擴(kuò)展域并查集吼砂。
例如，若只有兩個集合“敵人”和“朋友”周偎，且如下關(guān)系可以相互導(dǎo)出：
1 A和B是朋友，B和C是朋友蛉艾，可推出A和C是朋友
2 A和B是敵人逢享，B和C是敵人弓柱，可推出A和C是朋友
那么我們可以建立一個擴(kuò)展域并查集來維護(hù)關(guān)系禀横。
具體地說酿箭，我們將一個節(jié)點(diǎn)拆成兩個節(jié)點(diǎn)
和
，
表示
是朋友，
表示
是敵人，同理纵诞，我們將另一個節(jié)點(diǎn)
拆成
和
。
若題目輸入x和y是朋友，那么這意味著兩條信息：
1 和
是朋友
2 和
是朋友
因此合并（掉蔬，
）和（
壕翩，
）
若題目輸入x和y是敵人，那么這意味著兩條信息：
1 和
是朋友
2 和
是朋友
因此合并（珍策，
）和（
，
）
例題
POJ1733 Parity Game
用sum表示S序列的前綴和，則輸入分兩種情況
1 S[l...r]有偶數(shù)個1，即sum[r]和sum[l-1]奇偶性相同
2 S[l...r]有奇數(shù)個1祟蚀，即sum[r]和sum[l-1]奇偶性不同
顯然鹏溯，奇數(shù)域和偶數(shù)域天然對立匀借，也滿足剛才“朋友”和“敵人”集合的特點(diǎn)：
1 A和B奇偶性相同，B和C奇偶性相同，可推出A和C奇偶性相同
2 A和B奇偶性不同，B和C奇偶性不同，可推出A和C奇偶性相同
因此按照上面的方法處理輸入即可紫皇。
PS：由于l和r的范圍可能很大萄窜，需要離散化處理
代碼如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=5000*4+5;
const int INF=0x3f3f3f3f;
int temp,n,f[maxn],q,x[maxn],y[maxn],a[maxn],cnt=0;
string s[maxn];
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
int main() {
ios::sync_with_stdio(false);
// freopen("Parity Game.in","r",stdin);
cin>>temp;
cin>>q;
for(int i=1; i<=q; i++) {
cin>>x[i]>>y[i]>>s[i];
if(y[i]<x[i]) swap(x[i],y[i]);
a[++cnt]=x[i];
a[++cnt]=y[i];
}
sort(a+1,a+cnt+1);
n=unique(a+1,a+cnt+1)-a-1;
for(int i=1;i<=n*2;i++){
f[i]=i;
}
for(int i=1; i<=q; i++) {
int xx=lower_bound(a+1,a+n+1,x[i]-1)-a;
int yy=lower_bound(a+1,a+n+1,y[i])-a;
int fa=find(xx);
int fa1=find(xx+n);
int fb=find(yy);
int fb1=find(yy+n);
if(s[i]=="even") {
if(fa==fb1){
cout<<i-1<<endl;
return 0;
}
f[fa]=fb;
f[fa1]=fb1;
}
else{
if(fa==fb){
cout<<i-1<<endl;
return 0;
}
f[fa1]=fb;
f[fb1]=fa;
}
}
cout<<q<<endl;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ1182 食物鏈
這里的兩個對立集合變成了三個穗泵，但原理與上面相同。
代碼如下
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int n,k,ans=0,fa[3*5*10002],q,x,y;
void init()
{
for(int i=1;i<=3*n;i++) fa[i]=i;
}
int f(int x)
{
if (x==fa[x]) return x;
return fa[x]=f(fa[x]);
}
bool check1(int x,int y)
{
if (f(x+n)==f(y))
return false;
if (f(x)==f(y+n))
return false;
return true;
}
bool check2(int x,int y)
{
if (x==y) return false;
if (f(x)==f(y))
return false;
if (f(x)==f(y+n))
return false;
return true;
}
int main()
{
scanf("%d%d",&n,&k);
init();
for(int i=1;i<=k;i++)
{
scanf("%d%d%d",&q,&x,&y);
if (x>n||y>n)
{
ans++;
continue;
}
if (q==1)
{
if (check1(x,y))
{
fa[f(x)]=f(y);
fa[f(x+n)]=f(y+n);
fa[f(x+2*n)]=f(y+2*n);
}
else
ans++;
}
if (q==2)
{
if (check2(x,y))
{
fa[f(x+n)]=f(y);
fa[f(x)]=f(y+2*n);
fa[f(x+2*n)]=f(y+n);
}
else
ans++;
}
}
printf("%d",ans);
return 0;
}
樹狀數(shù)組
樹狀數(shù)組所有單次操作時間復(fù)雜度：
由于在設(shè)計(jì)時消去了冗余節(jié)點(diǎn)尺棋，并且將節(jié)點(diǎn)編號和二進(jìn)制聯(lián)系起來，樹狀數(shù)組的空間復(fù)雜度闷叉、常數(shù)和代碼量都比線段樹有了明顯的優(yōu)化握侧。然而，這些節(jié)點(diǎn)的消去嘿期，也讓樹狀數(shù)組難以維護(hù)求最值的操作品擎。
基本功能：單點(diǎn)增加，區(qū)間求和备徐，逆序?qū)?br>
代碼如下
void add(int x, int y) { //單點(diǎn)增加
for (; x <= N; x += x & -x) c[x] += y;
}
int ask(int x) { //區(qū)間求和
int ans = 0;
for (; x; x -= x & -x) ans += c[x];
return ans;
}
for (int i = n; i; i--) { //逆序?qū)Σ渌鬭[i]范圍較大缕坎，需要離散化
//然而離散化需要排序停局，所以還不如直接用歸并排序求逆序?qū)? ans += ask(a[i]-1);
add(a[i], 1);
}
PS：樹狀數(shù)組求逆序?qū)υ恚?strong>逆序掃描整個序列推汽，每次先查詢小于a[i]的數(shù)的個數(shù)累加進(jìn)入答案邪码，然后將a[i]插入樹狀數(shù)組斧拍。這就保證了每次查詢的范圍都是i之后的數(shù)字且值小于a[i]且不包括a[i]攒至。
例題
4201 樓蘭圖騰
記l[i]表示1...i-1中比a[i]大的數(shù)的個數(shù)
r[i]表示i+1...n中比a[i]大的數(shù)的個數(shù)
則“V”型圖騰的數(shù)量就是
另一種圖騰計(jì)算同理
代碼如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=200000+5;
const int INF=0x3f3f3f3f;
ll n,a[maxn],c[maxn],l1[maxn],l2[maxn],r1[maxn],r2[maxn],ans1=0,ans2=0;
void add(ll x){
for(int i=x;i<=n;i+=i&-i){
c[i]++;
}
}
ll sum(ll x){
ll sum=0;
for(int i=x;i>0;i-=i&-i){
sum+=c[i];
}
return sum;
}
int main() {
ios::sync_with_stdio(false);
// freopen("樓蘭圖騰.in","r",stdin);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]=n-a[i]+1;
}
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++){
l1[i]=sum(a[i]);
add(a[i]);
}
memset(c,0,sizeof(c));
for(int i=n;i>=1;i--){
r1[i]=sum(a[i]);
add(a[i]);
}
for(int i=1;i<=n;i++){
// cout<<l1[i]<<" "<<r1[i]<<endl;
ans1+=l1[i]*r1[i];
}
cout<<ans1<<" ";
for(int i=1;i<=n;i++){
a[i]=n-a[i]+1;
}
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++){
l2[i]=sum(a[i]);
add(a[i]);
}
memset(c,0,sizeof(c));
for(int i=n;i>=1;i--){
r2[i]=sum(a[i]);
add(a[i]);
}
for(int i=1;i<=n;i++){
// cout<<l2[i]<<" "<<r2[i]<<endl;
ans2+=l2[i]*r2[i];
}
cout<<ans2;
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
當(dāng)然荆几，通過一些技巧性的轉(zhuǎn)化抬纸，我們能將樹狀數(shù)組的適用范圍拓寬呜呐。
我們來看看如何通過前綴和和差分的轉(zhuǎn)化實(shí)現(xiàn)區(qū)間增加和單點(diǎn)查詢功能。
題意：長度為n的數(shù)列，q個操作。C l r d 表示把第l~r個數(shù)+d。Q x表示求第x個數(shù)的值撼短，n<1e5,q<1e5
我們知道，樹狀數(shù)組的基本操作可以實(shí)現(xiàn)單點(diǎn)修改吠撮，那么為了將區(qū)間修改轉(zhuǎn)化為單點(diǎn)修改尊惰，我們用樹狀數(shù)組維護(hù)序列的差分?jǐn)?shù)組，同時單點(diǎn)查詢也就變成了差分?jǐn)?shù)組上的前綴和操作。
我們繼續(xù)來考慮一個根據(jù)有一般性的問題
POJ3468 A Simple Problem with Integers
題目要求實(shí)現(xiàn)區(qū)間修改和區(qū)間求和
為了將區(qū)間修改轉(zhuǎn)化為單點(diǎn)修改弄屡，我們?nèi)杂脴錉顢?shù)組b維護(hù)序列變化的差分?jǐn)?shù)組题禀，具體地說，b數(shù)組初始全部為0膀捷，若輸入指令C l r d迈嘹，則令b[l]+d，b[r+1]-d全庸。
那么l~r上新增的量就是秀仲。
考慮如何求
將上式展開
此時我們將三個變量x，i壶笼，j消去變量j神僵，變成了兩個變量。
由于求和式中同時包含x和i覆劈，不易計(jì)算保礼。而樹狀數(shù)組擅于計(jì)算，因此责语，我們將x和i分離炮障，即將上式變形如下
因此我們建立兩個樹狀數(shù)組、
鹦筹，分別用于維護(hù)b[i]和i×b[i]铝阐。
具體地說，若輸入指令C l r d铐拐，則執(zhí)行以下四個操作
1 的l位置+d
2 的r+1位置-d
3 的l位置+l×d
4 的r+1位置-(r+1)×d
用sum數(shù)組維護(hù)原序列的前綴和徘键，對于指令Q l r，只需要輸出
代碼如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
ll c[2][maxn],n,q,a[maxn],sum[maxn];
void add(int k,int x,ll v){
for(int i=x;i<=n;i+=i&-i){
c[k][i]+=v;
}
}
ll ask(int k,int x){
ll ans=0;
for(int i=x;i>0;i-=i&-i){
ans+=c[k][i];
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
// freopen("A Simple Problem with Integers.in","r",stdin);
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
char op;
int l,r;
while(q--){
cin>>op>>l>>r;
ll d;
if(op=='C'){
cin>>d;
add(0,l,d);
add(0,r+1,-d);
add(1,l,(ll)l*d);
add(1,r+1,-(ll)(r+1)*d);
}
else{
cout<<sum[r]-sum[l-1]+(r+1)*ask(0,r)-ask(1,r)-(l*ask(0,l-1)-ask(1,l-1))<<endl;
}
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
POJ2182 Lost Cows
因?yàn)樗心膛Ｉ砀卟煌沂?~n的排列遍蟋，所以逆序考慮每一頭奶牛吹害，若最后一頭奶牛前面有頭奶牛比它矮，那么它的身高為
虚青。
考慮倒數(shù)第二頭奶牛它呀，若它前面有頭奶牛比它矮，那么：
1 若棒厘，則它的身高
2 若纵穿，則它的身高
以此類推，若第k頭奶牛前面有頭奶牛比它矮奢人，那么它的身高
就是1~n中第
小的谓媒，且沒有在
中出現(xiàn)過的數(shù)。
具體實(shí)現(xiàn)中何乎，我們建立一個01序列b句惯，初始全為1土辩，表示所有身高都沒有出現(xiàn)過。逆序掃描n頭奶牛抢野，對于每頭奶牛執(zhí)行如下操作：
1 查詢中第
個1在哪里拷淘，其位置就是第i頭奶牛的身高
2 將變成0（減去1）
方法一：樹狀數(shù)組+二分
每次二分答案，通過樹狀數(shù)組求前綴和尋找第個1
時間復(fù)雜度：
方法二：樹狀數(shù)組+倍增
因?yàn)闃錉顢?shù)組天然維護(hù)了區(qū)間長度為2的整數(shù)次冪的信息指孤，于是可以在的時間內(nèi)求解
附上兩種方法的代碼
/*
*/
#define method_2
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=8000+5;
const int INF=0x3f3f3f3f;
ll n,c[maxn],a[maxn],sum=0,ans[maxn];
void add(ll x,ll val){
for(int i=x;i<=n;i+=i&-i){
c[i]+=val;
}
}
ll ask(ll x){
ll sum=0;
for(int i=x;i>0;i-=i&-i){
sum+=c[i];
}
return sum;
}
int main() {
ios::sync_with_stdio(false);
freopen("Lost Cows.in","r",stdin);
memset(c,0,sizeof(c));
cin>>n;
// sum=(1+n)*n/2;
a[1]=0;
for(int i=1;i<=n;i++){
add(i,1);
}
for(int i=2;i<=n;i++){
cin>>a[i];
}
for(int i=n;i>=1;i--){
int l=1,r=n;
while(l<=r){
int mid=(l+r)>>1;
if(ask(mid)<a[i]+1) l=mid+1;
else r=mid-1;
}
ans[i]=l;
add(l,-1);
// sum-=ans[i];
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=8000+5;
const int INF=0x3f3f3f3f;
ll n,c[maxn],a[maxn],sum=0,ans[maxn];
void add(ll x,ll val){
for(int i=x;i<=n;i+=i&-i){
c[i]+=val;
}
}
ll ask(ll x){
ll sum=0;
for(int i=x;i>0;i-=i&-i){
sum+=c[i];
}
return sum;
}
int main() {
ios::sync_with_stdio(false);
// freopen("Lost Cows.in","r",stdin);
memset(c,0,sizeof(c));
cin>>n;
// sum=(1+n)*n/2;
a[1]=0;
for(int i=1;i<=n;i++){
add(i,1);
}
for(int i=2;i<=n;i++){
cin>>a[i];
}
for(int i=n;i>=1;i--){
ll ans1=0,sum=0;
for(int j=log2(n);j>=0;j--){
if(ans1+(1<<j)<=n&&sum+c[ans1+(1<<j)]<a[i]+1) sum+=c[ans1+(1<<j)],ans1+=(1<<j);
}
ans[i]=ans1+1;
add(ans1+1,-1);
}
for(int i=1;i<=n;i++){
cout<<ans[i]<<endl;
}
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
線段樹
線段樹的基本操作包括區(qū)間求和启涯，區(qū)間求最值（這里的最值是廣義的最值，不僅限于max和min）邓厕，單點(diǎn)修改逝嚎，單點(diǎn)查值。這些操作的時間復(fù)雜度均為详恼。
類型定義
struct SegmentTree {
int l, r;
int dat;
} t[SIZE * 4];
建樹
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r) { t[p].dat = a[l]; return; }
int mid = (l + r) / 2;
build(p*2, l, mid);
build(p*2+1, mid+1, r);
t[p].dat = max(t[p*2].dat, t[p*2+1].dat);
}
build(1, 1, n);
單點(diǎn)修改
void change(int p, int x, int v) {
if (t[p].l == t[p].r) { t[p].dat = v; return; }
int mid = (t[p].l + t[p].r) / 2;
if (x <= mid) change(p*2, x, v);
else change(p*2+1, x, v);
t[p].dat = max(t[p*2].dat, t[p*2+1].dat);
}
change(1, x, v);
區(qū)間求最值
int ask(int p, int l, int r) {
if (l <= t[p].l && r >= t[p].r) return t[p].dat;
int mid = (t[p].l + t[p].r) / 2;
int val = 0;
if (l <= mid) val = max(val, ask(p*2, l, r));
if (r > mid) val = max(val, ask(p*2+1, l, r));
return val;
}
cout << ask(1, l, r) << endl;
例題
4301 Can you answer on these queries III
考慮最大子段和的生成過程补君，在區(qū)間上維護(hù)六個信息：區(qū)間和sum，區(qū)間最大子段和dat昧互，緊貼左端點(diǎn)的最大子段和lmax挽铁，緊貼右端點(diǎn)的最大子段和rmax。
分三類討論敞掘，得到轉(zhuǎn)移如下
代碼如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=500000+5;
const int INF=0x3f3f3f3f;
int n,m,a[maxn];
struct node {
int l,r,sum,lmax,rmax,dat;
node(int tmp=0) {
sum=lmax=rmax=dat=tmp;
}
} tree[maxn<<2];
void build(int p,int l,int r) {
tree[p].l=l,tree[p].r=r;
if(l==r) {
tree[p].sum=tree[p].dat=tree[p].lmax=tree[p].rmax=a[l];
return;
}
int mid=(l+r)>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
tree[p].lmax=max(tree[p<<1].lmax,tree[p<<1].sum+tree[p<<1|1].lmax);
tree[p].rmax=max(tree[p<<1|1].rmax,tree[p<<1|1].sum+tree[p<<1].rmax);
// tree[p].dat=max(tree[p<<1].dat,tree[p<<1|1].dat);
tree[p].dat=max(tree[p<<1].dat,max(tree[p<<1|1].dat,tree[p<<1].rmax+tree[p<<1|1].lmax));
}
void change(int p,int x,int v) {
if(tree[p].l==tree[p].r) {
tree[p].sum=tree[p].dat=tree[p].lmax=tree[p].rmax=v;
return;
}
int mid=(tree[p].l+tree[p].r)>>1;
if(x<=mid) change(p<<1,x,v);
else change(p<<1|1,x,v);
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
tree[p].lmax=max(tree[p<<1].lmax,tree[p<<1].sum+tree[p<<1|1].lmax);
tree[p].rmax=max(tree[p<<1|1].rmax,tree[p<<1|1].sum+tree[p<<1].rmax);
tree[p].dat=max(tree[p<<1].dat,max(tree[p<<1|1].dat,tree[p<<1].rmax+tree[p<<1|1].lmax));
}
node ask(int p,int l,int r) {
if(l<=tree[p].l&&r>=tree[p].r) {
return tree[p];
}
int mid=(tree[p].l+tree[p].r)>>1;
// int val=-INF;
node a,b,c;
if(r<=mid) return ask(p<<1,l,r);
if(l>=mid+1) return ask(p<<1|1,l,r);
else{
a=ask(p<<1,l,r);
b=ask(p<<1|1,l,r);
c.sum=a.sum+b.sum;
c.lmax=max(a.lmax,a.sum+b.lmax);
c.rmax=max(b.rmax,b.sum+a.rmax);
c.dat=max(a.dat,max(b.dat,a.rmax+b.lmax));
return c;
}
}
void print(int p,int l,int r) {
if(l==r) cout<<p<<" "<<tree[p].lmax<<" "<<tree[p].rmax<<" "<<tree[p].sum<<" "<<tree[p].dat<<endl;
int mid=(l+r)>>1;
print(p<<1,l,mid);
print(p<<1|1,mid+1,r);
}
int main() {
ios::sync_with_stdio(false);
// freopen("Can you answer on these queries III.in","r",stdin);
cin>>n>>m;
for(int i=1; i<=n; i++) {
cin>>a[i];
}
build(1,1,n);
int x,y,z;
while(m--)
{
cin>>x>>y>>z;
// if(y>z) swap(y,z); //不能在這里swap 會影響命令2
if(x==1)cout<<ask(1,min(y,z),max(y,z)).dat<<endl;
else change(1,y,z);
}
return 0;
}
#endif
4302 Interval GCD
因?yàn)間cd(x,y,z)=gcd(x,y-x,z-y)
所以用線段樹維護(hù)原序列的差分序列的gcd叽掘。
又因?yàn)榍髤^(qū)間gcd的時候，需要區(qū)間第一個數(shù)的原始值玖雁，所以額外用一個樹狀數(shù)組維護(hù)原值更扁。
代碼如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=5e5+5;
const int INF=0x3f3f3f3f;
ll n,m;
struct SegmentTree {
int l,r;
ll dat;
} t[maxn<<2];
ll a[maxn],b[maxn],c[maxn];
ll gcd(ll x,ll y) {
return !y?x:gcd(y,x%y);
}
void build(int rt,int l,int r) {
t[rt].l=l;
t[rt].r=r;
if(l==r) {
t[rt].dat=b[l];
return;
}
int mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
t[rt].dat=gcd(t[rt<<1].dat,t[rt<<1|1].dat);
}
void change(int rt,int x,ll v) {
if(t[rt].l==t[rt].r) {
t[rt].dat+=v;
return;
}
int mid=t[rt].l+t[rt].r>>1;
if(mid>=x) change(rt<<1,x,v);
else change(rt<<1|1,x,v);
t[rt].dat=gcd(t[rt<<1].dat,t[rt<<1|1].dat);
}
ll ask(int rt,int l,int r) {
if(t[rt].l>=l&&t[rt].r<=r) return abs(t[rt].dat);
int mid=t[rt].l+t[rt].r>>1;
ll val=0;
if(l<=mid) val=gcd(val,ask(rt<<1,l,r));
if(r>mid) val=gcd(val,ask(rt<<1|1,l,r));
return abs(val);
}
void add(int x,ll v) {
for(int i=x; i<=n; i+=i&-i) {
c[i]+=v;
}
}
ll sum(int x) {
ll ans=0;
for(int i=x; i>=1; i-=i&-i) {
ans+=c[i];
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
// freopen("Interval GCD.in","r",stdin);
cin>>n>>m;
for(int i=1; i<=n; i++) {
cin>>a[i];
}
b[1]=a[1];
for(int i=2; i<=n; i++) {
b[i]=a[i]-a[i-1];
}
build(1,1,n);
// cout<<t[1].l<<" "<<t[1].r<<endl;
char op;
int l,r;
ll d;
while(m--) {
/*
for(int i=1;i<=n;i++){
D(a[i]+sum(i));
}
E;
*/
cin>>op;
if(op=='Q') {
cin>>l>>r;
ll al=a[l]+sum(l);
ll val=l<r?ask(1,l+1,r):0;
cout<<gcd(ask(1,l+1,r),al)<<endl;
} else {
cin>>l>>r>>d;
change(1,l,d);
if(r<n) change(1,r+1,-d);
add(l,d);
if(r<n) add(r+1,-d);
}
}
return 0;
}
#endif
通過“懶惰標(biāo)記/延遲標(biāo)記”的技巧，線段樹也能夠?qū)崿F(xiàn)內(nèi)完成區(qū)間修改和區(qū)間查詢赫冬。
例題
4301 Can you answer on these queries III
關(guān)于延遲標(biāo)記這里不做解釋浓镜，代碼如下
類型定義
struct SegmentTree{
int l,r;
long long sum,add;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define add(x) tree[x].add
}tree[SIZE*4];
建樹
void build(int p,int l,int r)
{
l(p)=l,r(p)=r;
if(l==r) { sum(p)=a[l]; return; }
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
sum(p)=sum(p*2)+sum(p*2+1);
}
傳遞標(biāo)記
void spread(int p) {
if(add(p)) {
sum(p*2)+=add(p)*(r(p*2)-l(p*2)+1);
sum(p*2+1)+=add(p)*(r(p*2+1)-l(p*2+1)+1);
add(p*2)+=add(p);
add(p*2+1)+=add(p);
add(p)=0;
}
}
區(qū)間修改
void change(int p,int l,int r,int z) {
if(l<=l(p)&&r>=r(p)) {
sum(p)+=(long long)z*(r(p)-l(p)+1);
add(p)+=z;
return;
}
spread(p);
int mid=(l(p)+r(p))/2;
if(l<=mid) change(p*2,l,r,z);
if(r>mid) change(p*2+1,l,r,z);
sum(p)=sum(p*2)+sum(p*2+1);
}
區(qū)間求和
long long ask(int p,int l,int r) {
if(l<=l(p)&&r>=r(p)) return sum(p);
spread(p);
int mid=(l(p)+r(p))/2;
long long ans=0;
if(l<=mid) ans+=ask(p*2,l,r);
if(r>mid) ans+=ask(p*2+1,l,r);
return ans;
}
另外，線段樹可以處理多維偏序問題的一個維度劲厌。因此膛薛，線段樹可以和排序結(jié)合求解二維偏序問題，可以和平衡樹結(jié)合構(gòu)成樹套樹求解三維/多維偏序問題补鼻。（類似的哄啄，樹狀數(shù)組結(jié)合排序可以求解某些不需要求最值的二維偏序問題，樹狀數(shù)組+排序+CDQ分治可以離線求解三維偏序問題）
這里講解線段樹維護(hù)掃描線+排序離散化求解二維偏序問題
例題
POJ1151 Atlantis
我們用一條豎直直線從左向右掃過整個坐標(biāo)系风范，那么直線上被并集圖形覆蓋的長度只會在每個矩形的左右邊界發(fā)生變化咨跌。
因此，我們只要知道掃描線在每段上被覆蓋的長度硼婿，乘以該段距離虑润，對所有這樣的值求和就是答案了。
具體實(shí)現(xiàn)中加酵，我們設(shè)每個矩形左上角為拳喻，右下角為
，矩形的左邊界四元組
猪腕，右邊界四元組
冗澈，c[i]表示掃描線上第i段被覆蓋的次數(shù)。
首先對y坐標(biāo)離散化陋葡，val(y)表示y被離散化后的整數(shù)值亚亲，raw[i]表示離散化后的i對應(yīng)到實(shí)際坐標(biāo)中的y值。
對于每個四元組腐缤，把c數(shù)組中的
捌归，相當(dāng)于覆蓋了
這個區(qū)間（因?yàn)閏數(shù)組的含義是區(qū)間，所以
到
的區(qū)間上限是
而不是
）岭粤。
若下一個四元組橫坐標(biāo)為惜索，那么這段面積就是
，對于每個四元素剃浇，樸素的在c數(shù)組上修改巾兆，時間復(fù)雜度為
（本題實(shí)現(xiàn)寬裕，這種方法已經(jīng)可以AC虎囚。
考慮用線段樹維護(hù)c數(shù)組角塑，把時間復(fù)雜度優(yōu)化到
方法一：運(yùn)用延遲標(biāo)記實(shí)現(xiàn)區(qū)間修改和查詢
方法二：由于我們只關(guān)心線段樹根節(jié)點(diǎn)（整個掃描線）上被矩形覆蓋的長度，并且四元組總是成對出現(xiàn)淘讥，所以線段樹上的區(qū)間修改也是成對的圃伶，這種情況下，沒有必要向下傳遞延遲標(biāo)記蒲列。換句話說窒朋，統(tǒng)計(jì)時只考慮根節(jié)點(diǎn)，所系不用向下傳遞標(biāo)記拭宁。
具體實(shí)現(xiàn)上腔剂，我們除了維護(hù)區(qū)間左右端點(diǎn)外宙攻，我們在線段樹的每個節(jié)點(diǎn)上維護(hù)兩個值：節(jié)點(diǎn)代表區(qū)間被覆蓋的長度len，節(jié)點(diǎn)被覆蓋次數(shù)cnt喉前，初始時兩者均為0。
對于四元組视事，我們在
上區(qū)間修改锈拨。該區(qū)間被線段樹劃分成
個節(jié)點(diǎn)，我們將這些節(jié)點(diǎn)的cnt+=k。
對于線段中任意一個節(jié)點(diǎn)[l,r]留潦，若cnt>0十偶，則len=raw(r+1)-raw(l)（同樣，由于線段樹維護(hù)的是區(qū)間，所以這里是r+1猛频，而不是r）训柴。否則幻馁，該點(diǎn)的len為兩個子節(jié)點(diǎn)的len之和（需特判葉子節(jié)點(diǎn)）膘滨。在一個節(jié)點(diǎn)的cnt被修改，以及線段樹從下向上回溯時稀拐，我們這樣更新len火邓，最后根節(jié)點(diǎn)的len就是整個掃描線上被覆蓋的長度。
代碼如下德撬，其中method_1是樸素做法铲咨，method_2是優(yōu)化做法中的方法二（spread函數(shù)和上面延遲標(biāo)記中的spread函數(shù)不同，這里的spread只含有向上合并的操作）蜓洪。
/*
*/
#define method_2
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=200+5;
const int INF=0x3f3f3f3f;
int n,num,c[maxn];
double raw[maxn];
struct node{
double X,Y1,Y2;
int f;
bool operator<(const node &h)const{
return X<h.X;
}
}line[maxn];
int val(double y){
return lower_bound(raw+1,raw+num+1,y)-raw;
}
int main() {
ios::sync_with_stdio(false);
//freopen("Atlantis.in","r",stdin);
int kase=0;
while(scanf("%d",&n)&&n){
printf("Test case #%d\n",++kase);
memset(c,0,sizeof(c));
memset(raw,0,sizeof(raw));
num=0;
double X1,Y1,X2,Y2;
for(int i=1;i<=n;i++){
scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);
line[2*i-1].X=X1;
line[2*i-1].Y1=Y1;
line[2*i-1].Y2=Y2;
line[2*i-1].f=1;
line[2*i].X=X2;
line[2*i].Y1=Y1;
line[2*i].Y2=Y2;
line[2*i].f=-1;
raw[++num]=Y1;
raw[++num]=Y2;
}
sort(line+1,line+2*n+1);
sort(raw+1,raw+num+1);
num=unique(raw+1,raw+num+1)-raw-1;
double ans=0.0;
for(int i=1;i<=2*n-1;i++){
double X=line[i].X;
double X2=line[i+1].X;
double Y1=line[i].Y1;
double Y2=line[i].Y2;
// printf("%lf %lf %lf %lf\n",X,X2,Y1,Y2);
// printf("%d %d\n",val(Y1),val(Y2));
int f=line[i].f;
for(int j=val(Y1);j<=val(Y2)-1;j++){
c[j]+=f;
}
for(int j=1;j<=num-1;j++){
if(c[j]>0){
// printf("%lf %lf\n",raw[j+1],raw[j]);
ans+=(X2-X)*(raw[j+1]-raw[j]);
}
}
}
printf("Total explored area: %.2lf\n\n",ans);
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=200+5;
const int INF=0x3f3f3f3f;
int n,num,c[maxn];
double raw[maxn];
struct node{
double X,Y1,Y2;
int f;
bool operator<(const node &h)const{
return X<h.X;
}
}line[maxn];
struct SegmentTree{
int l,r,cnt;
double len;
}tr[maxn<<2];
int val(double y){
return lower_bound(raw+1,raw+num+1,y)-raw;
}
void build(int rt,int l,int r){
tr[rt].l=l,tr[rt].r=r;
if(l==r){
tr[rt].cnt=0;
tr[rt].len=0;
return;
}
int mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
tr[rt].cnt=0;
tr[rt].len=0;
}
void spread(int p){
if(tr[p].cnt>0) tr[p].len=raw[tr[p].r+1]-raw[tr[p].l];
else if(tr[p].l==tr[p].r) tr[p].len=0; //這句話一定要有 作為葉子節(jié)點(diǎn)的邊界 否則會合并到未知位置
else tr[p].len=tr[p<<1].len+tr[p<<1|1].len;
}
void update(int rt,int l,int r,int v){
if(tr[rt].l>=l&&tr[rt].r<=r){
tr[rt].cnt+=v;
spread(rt);
return;
}
int mid=tr[rt].l+tr[rt].r>>1;
if(l<=mid) update(rt<<1,l,r,v);
if(r>mid) update(rt<<1|1,l,r,v);
spread(rt);
}
int main() {
ios::sync_with_stdio(false);
//freopen("Atlantis.in","r",stdin);
int kase=0;
while(scanf("%d",&n)&&n){
printf("Test case #%d\n",++kase);
memset(c,0,sizeof(c));
memset(raw,0,sizeof(raw));
num=0;
double X1,Y1,X2,Y2;
for(int i=1;i<=n;i++){
scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);
line[2*i-1].X=X1;
line[2*i-1].Y1=Y1;
line[2*i-1].Y2=Y2;
line[2*i-1].f=1;
line[2*i].X=X2;
line[2*i].Y1=Y1;
line[2*i].Y2=Y2;
line[2*i].f=-1;
raw[++num]=Y1;
raw[++num]=Y2;
}
sort(line+1,line+2*n+1);
sort(raw+1,raw+num+1);
num=unique(raw+1,raw+num+1)-raw-1;
build(1,1,num-1);
double ans=0.0;
for(int i=1;i<=2*n-1;i++){
double X=line[i].X;
double X2=line[i+1].X;
double Y1=line[i].Y1;
double Y2=line[i].Y2;
update(1,val(Y1),val(Y2)-1,line[i].f);
ans+=(X2-X)*tr[1].len;
}
printf("Total explored area: %.2lf\n\n",ans);
}
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
POJ2482 Stars in Your Window
由于矩形長寬確定且不可旋轉(zhuǎn)纤勒，我們討論矩形右上角的位置。
逆向思考蝠咆，我們發(fā)現(xiàn)踊东，對于星星(x,y)，能夠圈住它的矩形的右上角的坐標(biāo)范圍是(x,y)到(x+w,y+h)刚操，我們稱其為一個區(qū)域闸翅，區(qū)域的權(quán)值就是星星的亮度。將所有星星對應(yīng)的區(qū)域全部找出來后菊霜，問題轉(zhuǎn)化為若干個區(qū)域中坚冀，求在那個坐標(biāo)上區(qū)域重疊的權(quán)值和最大。
求區(qū)域重疊的權(quán)值和最大鉴逞，換句話說记某，我們需要維護(hù)一個求二維區(qū)間最值的數(shù)據(jù)結(jié)構(gòu)。類比上一題的做法构捡，我們從左至右掃描液南，同時關(guān)于縱坐標(biāo)建立一棵支持區(qū)間修改和維護(hù)區(qū)間最值的線段樹，對于四元組勾徽，在線段樹中滑凉，將對應(yīng)的區(qū)間
即可，最后根節(jié)點(diǎn)的dat用于更新答案。
PS：由于本題認(rèn)為矩形邊界上的星星不算畅姊，我們將矩形做縮放咒钟，即每個星星限定的區(qū)域是(x,y)到(x+w-1,y+h-1)
代碼如下（這里用延遲標(biāo)記實(shí)現(xiàn)了區(qū)間修改）
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=20000+5;
const int INF=0x3f3f3f3f;
struct SegmentTree{
ll l,r;
ll dat,add;
}t[maxn<<2];
struct node{
double X,Y1,Y2;
ll f;
bool operator<(const node &h)const{
return X!=h.X?X<h.X:f<h.f;
}
}a[maxn];
ll num,n,W,H,b[maxn];
void build(ll rt,ll l,ll r){
t[rt].l=l,t[rt].r=r;
t[rt].dat=t[rt].add=0;
if(l==r){
return;
}
ll mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
}
void spread(ll rt){
if(t[rt].add){
t[rt<<1].dat+=t[rt].add;
t[rt<<1].add+=t[rt].add;
t[rt<<1|1].dat+=t[rt].add;
t[rt<<1|1].add+=t[rt].add;
t[rt].add=0;
}
}
void change(ll rt,ll l,ll r,ll v){
if(t[rt].l>=l&&t[rt].r<=r){
t[rt].add+=v;
t[rt].dat+=v;
return;
}
spread(rt);
ll mid=(t[rt].l+t[rt].r)>>1;
if(mid>=l) change(rt<<1,l,r,v);
if(mid<r) change(rt<<1|1,l,r,v);
t[rt].dat=max(t[rt<<1].dat,t[rt<<1|1].dat);
}
int main() {
ios::sync_with_stdio(false);
// freopen("Stars in Your Window.in","r",stdin);
while(cin>>n>>W>>H){
ll x,y,z;
num=0;
for(int i=1;i<=n;i++){
cin>>x>>y>>z;
a[2*i-1].Y1=a[2*i].Y1=y;
a[2*i-1].Y2=a[2*i].Y2=y+H-1;
a[2*i-1].X=x;
a[2*i].X=x+W;
a[2*i-1].f=z;
a[2*i].f=-z;
b[++num]=y;
b[++num]=y+H-1;
}
sort(b+1,b+num+1);
num=unique(b+1,b+num+1)-b-1;
for(int i=1;i<=2*n;i++){
a[i].Y1=lower_bound(b+1,b+num+1,a[i].Y1)-b;
a[i].Y2=lower_bound(b+1,b+num+1,a[i].Y2)-b;
}
sort(a+1,a+2*n+1);
build(1,1,num);
ll ans=0;
for(int i=1;i<=2*n;i++){
change(1,a[i].Y1,a[i].Y2,a[i].f);
ans=max(ans,t[1].dat);
}
cout<<ans<<endl;
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
另外，有些計(jì)數(shù)問題中若未，線段樹可用于維護(hù)值域（權(quán)值線段樹）朱嘴，為了避免空間復(fù)雜度過高，權(quán)值線段樹會運(yùn)用動態(tài)開點(diǎn)的方式進(jìn)行粗合，這樣它沒有了完全二叉樹父子節(jié)點(diǎn)二倍編號的特性萍嬉，轉(zhuǎn)而用指針變量記錄左右兒子。（例題 6302 雨天的尾巴）
類型定義
struct node1 {
int lc,rc,dat,pos;
} tr[maxn*20*4]; //不動態(tài)開點(diǎn)的話 需要的空間就是maxn*maxn 因?yàn)閷τ诿總€點(diǎn)都要維護(hù)1e5種類型 這里的20=log2(maxn)
//也就是說動態(tài)開點(diǎn)的線段樹空間大概為maxn log（maxn）*4
//每進(jìn)行一次插入隙疚，會添加log級的點(diǎn)帚湘，因此開nlogn級數(shù)組即可。
初始化（開始的時候甚淡，n棵權(quán)值線段樹每棵線段樹只有根節(jié)點(diǎn)）
for(int i=1; i<=n; i++) {
root[i]=++num;
}
插入節(jié)點(diǎn)（維護(hù)區(qū)間最值和區(qū)間最值取到的位置）
void insert(int p,int l,int r,int val,int delta) {
if(l==r) {
tr[p].dat+=delta;
if(tr[p].dat==0) tr[p].pos=0;
else tr[p].pos=l;
return;
}
int mid=(l+r)>>1;
if(val<=mid) {
if(!tr[p].lc) tr[p].lc=++num;
insert(tr[p].lc,l,mid,val,delta);
} else {
if(!tr[p].rc) tr[p].rc=++num;
insert(tr[p].rc,mid+1,r,val,delta);
}
tr[p].dat=max(tr[tr[p].lc].dat,tr[tr[p].rc].dat);
tr[p].pos=tr[tr[p].lc].dat>=tr[tr[p].rc].dat?tr[tr[p].lc].pos:tr[tr[p].rc].pos;
}
線段樹合并（對應(yīng)計(jì)數(shù)問題中的值域合并過程）
int merge(int p,int q,int l,int r) {
if(!p) return q;
if(!q) return p;
if(l==r) {
tr[p].dat+=tr[q].dat;
if(tr[p].dat==0) tr[p].pos=0;
else tr[p].pos=l;
return p;
}
int mid=(l+r)>>1;
tr[p].lc=merge(tr[p].lc,tr[q].lc,l,mid);
tr[p].rc=merge(tr[p].rc,tr[q].rc,mid+1,r);
tr[p].dat=max(tr[tr[p].lc].dat,tr[tr[p].rc].dat);
tr[p].pos=tr[tr[p].lc].dat>=tr[tr[p].rc].dat?tr[tr[p].lc].pos:tr[tr[p].rc].pos;
return p;
}
BST和平衡樹
BST的原理這里不做解釋，直接上代碼捅厂。
建樹
struct BST {
int l, r;
int val;
}a[SIZE];
int tot, root, INF = 1<<30;
int New(int val) {
a[++tot].val = val;
return tot;
}
void Build() {
New(-INF), New(INF);
root = 1, a[1].r = 2;
}
檢索
int Get(int p, int val) {
if (p == 0) return 0;
if (val == a[p].val) return p;
return val < a[p].val ? Get(a[p].l, val) : Get(a[p].r, val);
}
插入
void Insert(int &p, int val) {
if (p == 0) {
p = New(val);
return;
}
if (val == a[p].val) return;
if (val < a[p].val) Insert(a[p].l, val);
else Insert(a[p].r, val);
}
求前驅(qū)/后繼 這里以后繼為例
int GetNext(int val) {
int ans = 2; // a[2].val==INF
int p = root;
while (p) {
if (val == a[p].val) {
if (a[p].r > 0) {
p = a[p].r;
while (a[p].l > 0) p = a[p].l;
ans = p;
}
break;
}
if (a[p].val > val && a[p].val < a[ans].val) ans = p;
p = val < a[p].val ? a[p].l : a[p].r;
}
return ans;
}
刪除
void Remove(int val) { //注意p是引用
int &p = root; //由于是引用 所以需要保存root的副本
while (p) {
if (val == a[p].val) break;
p = val < a[p].val ? a[p].l : a[p].r;
}
if (p == 0) return;
if (a[p].l == 0) p = a[p].r;
else if (a[p].r == 0) p = a[p].l;
else {
int next = a[p].r;
while (a[next].l > 0) next = a[next].l;
Remove(a[next].val);
a[next].l = a[p].l, a[next].r = a[p].r;
p = next;
}
}
若BST維護(hù)的是隨機(jī)序列贯卦，那么它的時間復(fù)雜度為，但是當(dāng)序列有序時焙贷，它的復(fù)雜度會退化成
撵割。由于滿足BST性質(zhì)且中序遍歷相同的二叉樹很多，而保證相同而形狀改變的操作叫旋轉(zhuǎn)辙芍。
通過旋轉(zhuǎn)啡彬，我們能讓一個不平衡的二叉樹逐漸變平衡。
左旋
void zig(int &p) { //注意這里p是引用而q不是引用
int q = a[p].l;
a[p].l = a[q].r, a[q].r = p, p = q;
Update(a[p].r), Update(p);
}
右旋
void zag(int &p) {
int q = a[p].r;
a[p].r = a[q].l, a[q].l = p, p = q;
Update(a[p].l), Update(p);
}
為了找到旋轉(zhuǎn)的條件故硅，我們在維護(hù)節(jié)點(diǎn)權(quán)值的同時庶灿，為每個節(jié)點(diǎn)分配一個隨機(jī)生成的額外權(quán)值，時刻維護(hù)這個額外權(quán)值滿足大根堆性質(zhì)吃衅，若不滿足時進(jìn)行旋轉(zhuǎn)即可往踢。
例題
4601 普通平衡樹
平衡樹模板題，這里不再贅述過程徘层，詳見代碼
PS：值得注意的是：
1 可能有數(shù)值重復(fù)峻呕，這時我們給每個節(jié)點(diǎn)一個cnt變量表示這個節(jié)點(diǎn)數(shù)值出現(xiàn)的次數(shù)，當(dāng)cnt=0時刪除節(jié)點(diǎn)即可趣效。
2 同時這里需要維護(hù)排名瘦癌。我們可以給每個節(jié)點(diǎn)維護(hù)一個size表示以該節(jié)點(diǎn)為根，其所有節(jié)點(diǎn)的cnt值之和跷敬，當(dāng)不存在重復(fù)數(shù)值時讯私，size即為子樹大小。使用遞歸更新size即可。
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
int n;
struct node {
int l,r;
int dat,val;
int cnt,size;
} a[maxn];
int tot=0,root;
int New(int val) {
a[++tot].val=val;
a[tot].dat=rand();
a[tot].cnt=a[tot].size=1;
return tot;
}
void Update(int p) {
a[p].size=a[p].cnt+a[a[p].l].size+a[a[p].r].size;
}
void Build() {
New(-INF*2);
New(INF*2);
root=1,a[1].r=2;
Update(root);
}
int GetRankByVal(int p,int val) {
if(p==0) return 0;
if(a[p].val==val) return a[a[p].l].size+1;
if(a[p].val<val) return GetRankByVal(a[p].r,val)+a[p].cnt+a[a[p].l].size;
return GetRankByVal(a[p].l,val);
}
int GetValByRank(int p,int rank) {
if(p==0) return INF;
if(a[a[p].l].size>=rank) return GetValByRank(a[p].l,rank);
if(a[a[p].l].size+a[p].cnt>=rank) return a[p].val;
return GetValByRank(a[p].r,rank-(a[a[p].l].size+a[p].cnt));
}
void zig(int &p) {
int q=a[p].l;
a[p].l=a[q].r,a[q].r=p,p=q;
Update(a[p].r);
Update(p);
}
void zag(int &p) {
int q=a[p].r;
a[p].r=a[q].l,a[q].l=p,p=q;
Update(a[p].l);
Update(p);
}
void Insert(int &p,int val) {
if(p==0) {
p=New(val);
return;
}
if(val==a[p].val) {
a[p].cnt++,Update(p);
return;
}
if(val<a[p].val) {
Insert(a[p].l,val);
if(a[p].dat<a[a[p].l].dat) zig(p);
}
if(val>a[p].val) {
Insert(a[p].r,val);
if(a[p].dat<a[a[p].r].dat) zag(p);
}
Update(p);
}
int GetPre(int val) {
int ans=1;
int p=root;
while(p) {
if(val==a[p].val) {
if(a[p].l>0) {
p=a[p].l;
while(a[p].r>0) p=a[p].r;
ans=p;
}
break;
}
if(a[p].val<val&&a[p].val>a[ans].val) ans=p;
p=val<a[p].val?a[p].l:a[p].r;
}
return a[ans].val;
}
int GetNext(int val) {
int ans=2;
int p=root;
while(p) {
if(val==a[p].val) {
if(a[p].r>0) {
p=a[p].r;
while(a[p].l>0) p=a[p].l;
ans=p;
}
break;
}
if(a[p].val>val&&a[p].val<a[ans].val) ans=p;
p=val<a[p].val?a[p].l:a[p].r;
}
return a[ans].val;
}
void Remove(int &p,int val) {
if(p==0) return;
if(val==a[p].val) {
if(a[p].cnt>1) {
a[p].cnt--;
Update(p);
return;
}
if(a[p].l||a[p].r) {
if(a[p].r==0||a[a[p].l].dat>a[a[p].r].dat) { //zig之后 a[p].r是a[p].l的父節(jié)點(diǎn)
zig(p),Remove(a[p].r,val); //注意：這樣傳遞不會改變root的值妄帘，除非對p做出賦值才會改變root
} else {
zag(p),Remove(a[p].l,val);
}
Update(p);
} else p=0;
return;
}
val<a[p].val?Remove(a[p].l,val):Remove(a[p].r,val);
Update(p);
}
int main() {
ios::sync_with_stdio(false);
// freopen("普通平衡樹.in","r",stdin);
cin>>n;
Build();
int op,x;
for(int i=1; i<=n; i++) {
cin>>op>>x;
if(op==1) {
Insert(root,x);
}
if(op==2) {
Remove(root,x);
}
if(op==3) {
cout<<GetRankByVal(root,x)-1<<endl;
}
if(op==4) {
cout<<GetValByRank(root,x+1)<<endl;
}
if(op==5) {
cout<<GetPre(x)<<endl;
}
if(op==6) {
cout<<GetNext(x)<<endl;
}
}
return 0;
}
#endif
