线段树一种初级数据结构(之前一度是高级),相信大多数学习数据结构的人都能熟练地掌握它.
线段树最初开发的意义是高效率地作用于区间操作(对数据的维护),但这个所谓的高效率也并不很高.但,相对于目前已经开发出来的一般性数据结构,线段树无疑是非常优秀且稳定的一个.
(Theta ( n imes log_2{n} )) 这是线段树建树操作的复杂度,对应地,每一次区间操作(修改和查询)都是 (log_2{n}) 的复杂度,其中,n为元素个数(序列长度).对于这种复杂度,大概可承受的元素个数约为 (10^6)
以上数据范围以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为元素个数
线段树的空间复杂度有 (n imes 2) 和 (n imes 4) 两种.我这里使用了较为简便的第二种...
那么根据定义,建树的操作也比较显然:
#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,原因显然.
}
这个时候,聪明的读者已经想到了,如果只进行上述修改,那么其余应该修改的节点(即恰好包含的那些节点的子树中的点)并没有被修改到.而如果每次都进行修改到叶子节点的操作,单次操作的时间复杂度就又退化成了$ Theta ( n imes log_2{n} )$ 这并不是我们想要的.那么如何在保证正确性的情况下保证复杂度不退化呢?
细心的读者已经发现了,之前的 (ADT) 中有一个懒标记 (tag) 还并没有用到.
答案就在这里,使用懒标记 ((lazytag)) 的方法来保证正确性和复杂度.
具体做法为,先按照给出代码的方式更新,当遇到恰好包含的节点时,更新节点值的同时更新标记.
那么标记是标记了,怎么用呢?
一个很自然的想法是,每次走到一个节点,若该节点的 (tag) 不为 (0) (即有过修改操作但未更新其子节点),就把标记下传给它的子节点(如果存在)并更新自身,不存在子节点的则直接更新自身.
这样,我们保证了每次访问到的节点一定是正确的,正确性得以保证.
复杂度呢?由于我们只是增加了几句赋值语句,所以并没有对复杂度造成什么影响,仍然为 (Theta ( n imes log_2{n} )) .
增加懒标记后的更新和查询代码如下:(依然以区间和为例子)
// 这份代码是加了取模的,因为题目要求取模,平时使用去掉取模运算即可
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;
}
由于某些种类的线段树我写的时候年代比较久远...所以代码风格以及写法可能不尽相同.各位将就着看吧.
水平有限,如有谬误,恳请斧正.