生活随笔
收集整理的這篇文章主要介紹了
AcWing 253. 普通平衡树
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
您需要寫一種數據結構（可參考題目標題），來維護一些數，其中需要提供以下操作：
插入數值x。刪除數值x(若有多個相同的數，應只刪除一個)。查詢數值x的排名(若有多個相同的數，應輸出最小的排名)。查詢排名為x的數值。求數值x的前驅(前驅定義為小于x的最大的數)。求數值x的后繼(后繼定義為大于x的最小的數)。
注意： 數據保證查詢的結果一定存在。
本題為平衡樹基本操作的代碼實現
using namespace std
;const int N
= 100010, INF
= 1e8
;int n
;
struct Node
{int l, r
;int key, val
;int cnt, size
;
}tr
[N
];int root, idx
;void pushup
(int p
)
{tr
[p
].size
= tr
[tr
[p
].l
].size + tr
[tr
[p
].r
].size + tr
[p
].cnt
;
}int get_node
(int key
)
{tr
[ ++ idx
].key
= key
;tr
[idx
].val
= rand
();tr
[idx
].cnt
= tr
[idx
].size
= 1;return idx
;
}void zig
(int
&p
) // 右旋
{int q
= tr
[p
].l
;tr
[p
].l
= tr
[q
].r, tr
[q
].r
= p, p
= q
;pushup
(tr
[p
].r
), pushup
(p
);
}void zag
(int
&p
) // 左旋
{int q
= tr
[p
].r
;tr
[p
].r
= tr
[q
].l, tr
[q
].l
= p, p
= q
;pushup
(tr
[p
].l
), pushup
(p
);
}void
build()
{get_node
(-INF
), get_node
(INF
);root
= 1, tr
[1].r
= 2;pushup
(root
);if (tr
[1].val
< tr
[2].val
) zag
(root
);
}void insert
(int
&p, int key
)
{if (!p
) p
= get_node
(key
);else if (tr
[p
].key
== key
) tr
[p
].cnt ++
;else if (tr
[p
].key
> key
){insert
(tr
[p
].l, key
);if (tr
[tr
[p
].l
].val
> tr
[p
].val
) zig
(p
);}else{insert
(tr
[p
].r, key
);if (tr
[tr
[p
].r
].val
> tr
[p
].val
) zag
(p
);}pushup
(p
);
}void remove
(int
&p, int key
)
{if (!p
) return;if (tr
[p
].key
== key
){if (tr
[p
].cnt
> 1) tr
[p
].cnt --
;else if (tr
[p
].l
|| tr
[p
].r
){if (!tr
[p
].r
|| tr
[tr
[p
].l
].val
> tr
[tr
[p
].r
].val
){zig
(p
);remove
(tr
[p
].r, key
);}else{zag
(p
);remove
(tr
[p
].l, key
);}}else p
= 0;}else if (tr
[p
].key
> key
) remove
(tr
[p
].l, key
);else remove
(tr
[p
].r, key
);pushup
(p
);
}int get_rank_by_key
(int p, int key
) // 通過數值找排名
{if (!p
) return 0; // 本題中不會發生此情況
if (tr
[p
].key
== key
) return tr
[tr
[p
].l
].size +
1;if (tr
[p
].key
> key
) return get_rank_by_key
(tr
[p
].l, key
);return tr
[tr
[p
].l
].size + tr
[p
].cnt + get_rank_by_key
(tr
[p
].r, key
);
}int get_key_by_rank
(int p, int rank
) // 通過排名找數值
{if (!p
) return INF
; // 本題中不會發生此情況
if (tr
[tr
[p
].l
].size
>= rank
) return get_key_by_rank
(tr
[p
].l, rank
);if (tr
[tr
[p
].l
].size + tr
[p
].cnt
>= rank
) return tr
[p
].key
;return get_key_by_rank
(tr
[p
].r, rank - tr
[tr
[p
].l
].size - tr
[p
].cnt
);
}int get_prev
(int p, int key
) // 找到嚴格小于key的最大數
{if (!p
) return -INF
;if (tr
[p
].key
>= key
) return get_prev
(tr
[p
].l, key
);return max
(tr
[p
].key, get_prev
(tr
[p
].r, key
));
}int get_next
(int p, int key
) // 找到嚴格大于key的最小數
{if (!p
) return INF
;if (tr
[p
].key
<= key
) return get_next
(tr
[p
].r, key
);return min
(tr
[p
].key, get_next
(tr
[p
].l, key
));
}int
main()
{build
();scanf
("%d",
&n
);while (n --
){int opt, x
;scanf
("%d%d",
&opt,
&x
);if (opt
== 1) insert
(root, x
);else if (opt
== 2) remove
(root, x
);else if (opt
== 3) printf
("%d\n", get_rank_by_key
(root, x
) -
1);else if (opt
== 4) printf
("%d\n", get_key_by_rank
(root, x +
1));else if (opt
== 5) printf
("%d\n", get_prev
(root, x
));else printf
("%d\n", get_next
(root, x
));}return 0;
}
Vector版偷懶平衡樹
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std
;
vector
<int>v
;
int n
,opt
,x
;
int main()
{v
.reserve(100001);scanf("%d",&n
);while(n
--){scanf("%d%d",&opt
,&x
);if(opt
==1) v
.insert(lower_bound(v
.begin(),v
.end(),x
),x
);if(opt
==2) v
.erase (lower_bound(v
.begin(),v
.end(),x
));if(opt
==3) printf("%d\n",lower_bound(v
.begin(),v
.end(),x
)-v
.begin()+1);if(opt
==4) printf("%d\n",v
[x
-1]);if(opt
==5) printf("%d\n",v
[lower_bound(v
.begin(),v
.end(),x
)-v
.begin()-1]);if(opt
==6) printf("%d\n",v
[upper_bound(v
.begin(),v
.end(),x
)-v
.begin()]);}return 0;
}
總結
以上是生活随笔為你收集整理的AcWing 253. 普通平衡树的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
