淺談線段樹
線段樹一種初級數據結構(之前一度是高級),相信大多數學習數據結構的人都能熟練地掌握它.
線段樹最初開發的意義是高效率地作用於區間操作(對數據的維護),但這個所謂的高效率也並不很高.但,相對於目前已經開發出來的一般性數據結構,線段樹無疑是非常優秀且穩定的一個.
這是線段樹建樹操作的複雜度,對應地,每一次區間操作(修改和查詢)都是
的複雜度,其中,n為元素個數(序列長度).對於這種複雜度,大概可承受的元素個數約為
以上數據範圍以CCF在NOIP系列競賽中使用的評測機為標準.
線段樹是一種二叉搜索樹，與區間樹相似，它將一個區間劃分成一些單元區間，每個單元區間對應線段樹中的一個葉結點。[1]
對於線段樹中的每一個非葉子節點[a,b]，它的左兒子表示的區間為[a,(a+b)/2]，右兒子表示的區間為[(a+b)/2+1,b]。因此線段樹是平衡二叉樹，最後的子節點數目為N，即整個線段區間的長度。——來自百度百科
可以看出,線段樹的一種非常自然的實現方式是遞歸.
先來一個線段樹的ADT(以區間和為例)
struct segtree {
int left , right , data , tag ;//分別為左端點,右端點,區間信息,懶標記
inline int size () { return right - left + 1 ; }//當前節點所管理的區間長度
}t[(N<<2)];//N為元素個數
線段樹的空間複雜度有 和
兩種.我這裡使用了較為簡便的第二種..
那麼根據定義,建樹的操作也比較顯然:
#define mid ( ( (l) + (r) ) >> 1 )
#define ls ( ( rt ) << 1 )
#define rs ( ( rt ) << 1 | 1 )
#define pushup(rt) t[rt].data = t[ls].data + t[rs].data // 用兒子來更新父親
inline void build (int rt , int l , int r) {
t[rt].left = l ; t[rt].right = 1 ; t[rt].tag = 0 ;
if ( l == r ) { t[rt].data = v[l] ; return ; }//到達葉子節點即賦為原序列中的值.
build ( ls , l , mid ) ; build ( rs , mid + 1 , r ) ;//遞歸建樹
pushup ( rt ) ; return ; // 這裡給出的是區間和線段樹的pushup
}
線段樹的區間查詢與區間修改也十分易於理解:
從根節點開始,若當前節點恰好包含待操作區間的某一部分,更新/查詢,否則,比較當前節點的區間中點與待操作區間的關係,左包含即向左遞歸,右包含即向右遞歸.
代碼也十分簡單(以區間和為例)
// 宏的定義與第一份代碼相同
inline void upadte (int rt , int ll , int rr , int val) {
int l = t[rt].left , r = t[rt].right ; // 取出當前節點的左右端點作為比較依據
if ( ll <= l && r <= rr ) { // 若恰好包含待操作區間的某一部分
t[rt].data += t[rt].size () * val ; // 處理當前節點的值,注意要乘上區間長度(考慮乘法分配律)
return ;
}
if ( ll <= mid ) update ( ls , ll , rr , val ) ; // 若左邊還有,向左遞歸
if ( rr > mid ) update ( rs , ll , rr , val ) ; // 若右邊還有,向右遞歸
pushup ( rt ) ; return ; // 別忘了pushup回去
}
inline void query (int rt , int ll , int rr ) {
int l = t[rt].left , r = t[rt].right ;
if ( ll <= l && r <= rr ) { ans += t[rt].data ; return ; } // 查詢與更新的區別之一,結果記錄在全局變數ans中
if ( ll <= mid ) query ( ls , ll , rr ) ;
if ( rr > mid ) query ( rs , ll , rr ) ;
return ; // query不需要pushup,原因顯然.
}
這個時候,聰明的讀者已經想到了,如果只進行上述修改,那麼其餘應該修改的節點(即恰好包含的那些節點的子樹中的點)並沒有被修改到.而如果每次都進行修改到葉子節點的操作,單次操作的時間複雜度就又退化成了 這並不是我們想要的.那麼如何在保證正確性的情況下保證複雜度不退化呢?
細心的讀者已經發現了,之前的ADT中有一個懶標記tag還並沒有用到.
答案就在這裡,使用懶標記(lazytag)的方法來保證正確性和複雜度.
具體做法為,先按照給出代碼的方式更新,當遇到恰好包含的節點時,更新節點值的同時更新標記.
那麼標記是標記了,怎麼用呢?
一個很自然的想法是,每次走到一個節點,若該節點的tag不為0(即有過修改操作但未更新其子節點),就把標記下傳給它的子節點(如果存在)並更新自身,不存在子節點的則直接更新自身.
這樣,我們保證了每次訪問到的節點一定是正確的,正確性得以保證.
複雜度呢?由於我們只是增加了幾句賦值語句,所以並沒有對複雜度造成什麼影響,仍然為 .
增加懶標記後的更新和查詢代碼如下:(依然以區間和為例子)
// 這份代碼是加了取模的,因為題目要求取模,平時使用去掉取模運算即可
inline void pushdown ( int rt ) { // 下傳標記操作
t[ls].tag = ( t[rt].tag + t[ls].tag ) % mod ;
t[rs].tag = ( t[rt].tag + t[rs].tag ) % mod ; // 把標記加給子節點
t[ls].data = ( t[ls].data + t[rt].tag * t[ls].size () ) % mod ;
t[rs].data = ( t[rs].data + t[rt].tag * t[rs].size () ) % mod ; // 別忘了乘上區間長度
t[rt].tag = 0 ; return ; // 別忘了把根節點的標記置為零,表示已經處理完標記.
}
inline void update (int rt , int ll , int rr , int wt) {
int l = t[rt].left , r = t[rt].right ;
if ( ll <= l && r <= rr ) {
t[rt].data = ( t[rt].data + wt * t[rt].size () ) % mod ;
t[rt].tag = ( t[rt].tag + wt ) % mod ; return ;
}
if ( t[rt].tag != 0 ) pushdown ( rt ) ; // 遇到標記必須先下傳
if ( ll <= mid ) update ( ls , ll , rr , wt ) ;
if ( rr > mid ) update ( rs , ll , rr , wt ) ;
pushup ( rt ) ; return ;
}
inline void query (int rt , int ll , int rr) {
int l = t[rt].left , r = t[rt].right ;
if ( ll <= l && r <= rr ) { res = ( res + t[rt].data ) % mod ; return ; }
if ( t[rt].tag != 0 ) pushdown ( rt ) ; // 先下傳
if ( ll <= mid ) query ( ls , ll , rr ) ;
if ( rr > mid ) query ( rs , ll , rr ) ;
return ;
}
至此,區間和的線段樹就已經完成了.
當然,線段樹並不只有區間和一種形態,還有區間異或,區間取反,區間最大(小)值,權值線段樹,可持久化(主席樹),zkw等等.
但無論是哪一種線段樹,都是以最基本的區間和線段樹為藍本構建的.只要熟練的掌握了區間和線段樹,其餘種類的線段樹理解起來並不困難.
在這裡附上區間最大(小)值線段樹和區間取反線段樹以及帶有離散化的主席樹的代碼:
區間最大值:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
#define N (int)1e5+5
#define pushup(rt) t[rt].data=max(t[ls].data,t[rs].data)
#define max(a,b) a>b?a:b
using namespace std;
int n,m,v[N];
int a,b,ans;
struct segtree{
int data,left,right,maxn;
}t[(N<<2)];
inline void build(int rt,int l,int r){
t[rt].left=l;t[rt].right=r;
if(l==r){
t[rt].data=v[l];
return ;
}
build(ls,l,mid);build(rs,mid+1,r);
pushup(rt);return ;
}
inline void query(int rt){
int l=t[rt].left,r=t[rt].right;
if(a<=l&&r<=b){
ans=max(ans,t[rt].data);
return ;
}
if(a<=mid) query(ls);
if(b>mid) query(rs);
return ;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&v[i]);
build(1,1,n);
for(int i=1;i<=m;++i){
scanf("%d%d",&a,&b);
query(1);
printf("%d
",ans);
ans=-0x3f3f3f3f;
}
return 0;
}
帶離散化的主席樹:
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#define mid ( ( l + r ) >> 1 )
#define rep(i,a,b) for (int i = a ; i <= b ; ++ i)
#define pushup(rt) t[rt].data = t[t[rt].left].data + t[t[rt].right].data
#define int long long
const int N = 200010 ;
struct seg { int left , right , data ; } t [ ( N * 20 ) ] ;
int n , m , v[N] , w[N] , cnt , rt[N] ;
inline void insert (int & rt , int l , int r , int val) {
t[++cnt] = t[rt] ; rt = cnt ;
if ( l == r ) { ++ t[rt].data ; return ; }
if ( val <= mid ) insert ( t[rt].left , l , mid , val ) ;
else insert ( t[rt].right , mid + 1 , r , val ) ;
pushup ( rt ) ; return ;
}
inline int query (int u , int v , int l , int r , int rank) {
if ( l == r ) return l ;
int T = t[t[v].left].data - t[t[u].left].data ;
if ( rank <= T ) return query ( t[u].left , t[v].left , l , mid , rank ) ;
else return query ( t[u].right , t[v].right , mid + 1 , r , rank - T ) ;
}
signed main () {
scanf ("%lld%lld" , & n , & m ) ;
rep ( i , 1 , n ) scanf ("%lld" , & v[i] ) , w[i] = v[i] ;
std::sort ( w + 1 , w + n + 1 ) ; w[0] = std::unique ( w + 1 , w + n + 1 ) - w - 1 ;
rep ( i , 1 , n ) v[i] = std::lower_bound ( w + 1 , w + w[0] + 1 , v[i] ) - w ;
rt[0] = 0 ; rep ( i , 1 , n ) rt[i] = rt[i - 1] , insert ( rt[i] , 1 , w[0] , v[i] ) ;
rep ( i , 1 , m ) {
register int l , r , k , ans ;
scanf ("%lld%lld%lld" , & l , & r , & k ) ;
ans = w [ query ( rt[l - 1] , rt[r] , 1 , w[0] , k ) ] ;
printf ("%lld
" , ans ) ;
}
return 0 ;
}
區間取反:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define mid ( ( l + r ) >> 1 )
#define ls ( rt << 1 )
#define rs ( rt << 1 | 1 )
#define pushup(rt) t[rt].data = t[ls].data + t[rs].data
#define N 200005
using namespace std;
int k , a , b ;
int ans , n , m ;
struct segtree{
int left , right , data , tag ;
inline int size() { return right - left + 1 ; }
}t[(N<<1)];
inline void build (int rt , int l , int r) {
t[rt].left = l ; t[rt].right = r ; t[rt].tag = 0 ;
if( l == r ) { t[rt].data = false ; return ; }
build ( ls , l , mid ) ; build ( rs , mid+1 , r ) ;
return ; // 因為一開始全是0所以就沒有pushup,注意一下就好
}
inline void pushdown(int rt){
if ( t[rt].tag ) {
t[ls].tag ^= 1 ;
t[rs].tag ^= 1 ;
t[ls].data = t[ls].size() - t[ls].data ;
t[rs].data = t[rs].size() - t[rs].data ;
t[rt].tag = 0 ;
}
return ;
}
inline void update(int rt) {
int l = t[rt].left , r = t[rt].right ;
if( a <= l && r <= b ){
t[rt].tag ^= 1 ;
t[rt].data = t[rt].size() - t[rt].data ;
return ;
}
pushdown ( rt ) ;
if ( a <= mid ) update ( ls ) ;
if ( b > mid ) update ( rs ) ;
pushup ( rt ) ; return ;
}
inline void query(int rt) {
int l = t[rt].left , r = t[rt].right ;
if ( a <= l && r <= b ) { ans += t[rt].data ; return ; }
pushdown ( rt ) ;
if ( a <= mid ) query ( ls ) ;
if ( b > mid ) query ( rs ) ;
return ;
}
int main(){
scanf("%d%d" , & n , & m ) ; build ( 1 , 1 , n ) ;
for(int i = 1 ; i <= m ; ++ i){
scanf("%d%d%d" , & k , & a , & b ) ;
if( k == 0 ) update ( 1 ) ;
else{
query ( 1 ) ;
printf ( "%d
" , ans ) ;
ans = 0 ;
}
}
return 0;
}
由於某些種類的線段樹我寫的時候年代比較久遠...所以代碼風格以及寫法可能不盡相同.各位將就著看吧.
水平有限,如有謬誤,懇請斧正.
歡迎訪問博客:
Phecda - 博客園
推薦閱讀：
