posts - 274, comments - 1258, trackbacks - 0

　　相信对算法设计或者数据结构有一定了解的人对线段树都不会太陌生。它是能够在log(MaxLen)时间内完成线段的添加、删除、查询等操作。但一般的实现都有点复杂（我自写的是要递归的，比较多行）。而线段树应用中有一种是专门针对点的。（点树？）它的实现却非常简单。
　　这种数据结构有什么用？我们先来考虑一下下面的需求（全部要求在LogN时间内完成）：如何知道一个点在一个点集里的大小“排名”？很简单，开一个点数组，排个序，再二分查找就行了；如何在一个点集内动态增删点？也很简单，弄个平衡树就行了（本来平衡树比线段树复杂得多，但自从世界上有了STL set这么个好东东，就……^_^）那如果我既要动态增删点，也要随时查询到一个点的排名呢？那对不起，可能就要出动到我们的“点树”了。
　　其实现原理很简单：每当增加（或删除）一个大小为X的点时，就在树上添加（或删除）一条(X,MaxLen)的线段（不含端点），当要查询一个点的排名时，只要看看其上有多少条线段就可以了。针对这一需求，这里有个非常简单的实现（见以下代码，十多行，够短了吧？）其中clear()用于清空点集；add()用于添加一个点；cntLs()返回小于n的点的个数，也就是n的升序排名，类似地cntGt是降序排名。
　　这个点树有什么用呢？其中一个应用时在O(NlogN)时间内求出一个排列的逆序数（http://acm.zju.edu.cn/show_problem.php?pid=1484，你有更好的算法吗？欢迎交流）方法是每读到一个数x，就让逆序数+=cntGt(x);然后再add(x)。
　　这个实现还可以进行一些扩展。比如删除del(int n)，只要把add(int n)中的++size换成--size，把a[i/2]++改成a[i/2]--即可。另外还可以通过二分查找功能在O(logN)时间内查到排名第n的点的大小。应该也可以三四行内搞定。

template < int N > // 表示可用区间为[0,N)，其中N必须是2的幂数;

class PointTree {

int a[ 2 * N];

int size;

void clear() { memset( this , 0 , sizeof ( * this ));}

void add( int n) {

int i = N + n; ++ size;

for ( ++ a[i]; i > 1 ; i /= 2 )

if ( ~ i & 1 ) a[i / 2 ] ++ ;

}

int cntLs( int n) { // 统计小于

int i = N + n,c = 0 ; // 若统计小于等于则c=a[i];

for (; i > 1 ; i /= 2 )

if (i & 1 ) c += a[i / 2 ];

return c;

}

int cntGt( int n) { return size - a[N + n] - cntLs(n); }

} ;

　　嗯~~~为了解http://acm.zju.edu.cn/show_problem.php?pid=2425这一题，还是把上述两个扩展给实现了啦，果然不难：

（接上）

void del(int n){

if(!a[n+=N])return;

--size;

for(--a[n]; n>1; n/=2)

if(~n&1)--a[n/2];

}

/* 解决：求点集中第i小的数(由0数起)

* 注意：如果i>=size 返回N-1

int operator[](int n){

int i=1;

while(i<N){

if(n<a[i]) i*=2;

else n-=a[i], i=i*2+1;

}

return i-N;

}

};

//附一个测试程序

#include<iostream.h>

T<8192> t;

int main(){

char c; int n;

while(cin>>c){

if(c=='c') t.clear();

else{

cin>>n;

if(c=='a') t.add(n);

if(c=='d') t.del(n);

if(c=='q') cout<<t[n]<<endl;

}

return 0;

}

P.S.：
　　在写完这篇文章一段时间后，我认识了另一种功能上比较类似的数据结构，叫做“树状数组”。它们有不少相似之处：

针对点集的处理（添加、删除、查找）；
相似的时空复杂度（logN时间，2N空间）；
相似的编程复杂度（都比线段树简短得多）；

因此，所有可以用树状数组解决的问题都可以用这个“点树”来解决，另外它还有以下好处：

更直观的转移（个人感受，不一定要同意）；
同时支持自下而上和自上而下两种方向的查找和更新，而后者树状数组不支持，所以树状数组不提供某些功能，比如说O(logN)求点集中第k小数。

posted on 2006-09-13 19:54 踏雪赤兔阅读(14749) 评论(43) 编辑收藏引用所属分类: 玩转编程

FeedBack:

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2006-09-13 21:06 | 喜欢游荡

看不懂...不过好象很专业的样子哦....恩..继续加油~! 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2006-09-13 21:14 | 小bug

“O(NlogN)时间内求出一个排列的逆序数”

经典的做法是对原序列作归并排序，在排序中统计~
不过你这个程序就真是短得离谱~~~继续努力~~~ 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2006-09-13 21:51 | 踏雪赤兔

原来是用归并排序~~多谢虫虫夸奖了＊＾＿＾＊回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2007-03-12 14:29 | nick

不好意思, 我還是不大懂你的程序

你有 MSN 嗎？

方便問你嗎？回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2007-03-13 00:48 | 踏雪赤兔

用QQ吧：38136419。
我不太习惯用MSN~ 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2007-04-28 18:25 | 尚敏

谢谢大牛分享！回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2007-05-23 14:52 | 踏雪赤兔

救命!我竟然忘了一个极重要的操作——求点集里n的个数了!大家BS我吧~~~现在补上啊~~

int cntEQ(int n){

return a[N+n];

}

因为它实在是太简单了~我通常都是直接写a[N+n]的~~

回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2007-06-08 17:49 | haha

set 也可以知道前面有多少个。看看lower_bound(); 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2007-06-08 17:53 | 踏雪赤兔

lower_bound()只能得到位置，如果要算前面有多少个必须逐个枚举，复杂度高达O(n) 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2007-08-22 11:19 | wshong

好东西,顶你回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2007-09-27 20:21 | y05zh

看那
看不懂回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2007-10-06 20:12 | Fify

我原来也是归并排序，复杂度也是NlogN，但是第归起来就慢死了~还是你的比较好，呵呵~ 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2007-10-06 20:14 | Fify

@踏雪赤兔

你不是已经重载了[]了吗？呵呵，那个多方便啊~

救命!我竟然忘了一个极重要的操作——求点集里n的个数了!大家BS我吧~~~现在补上啊~~
int cntEQ(int n){
return a[N+n];
} 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2007-10-06 21:22 | 踏雪赤兔

两者是不同的~
重截了的operator[]返回点集中的第n小元
而cntEQ()返回点集中n的个数回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2007-10-07 21:41 | 云龙天罚

有没有PAS的代码啊 C++的看不懂哦~~~~~
郁闷没有学C++ 乌拉拉~~~~~ 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2007-10-08 00:52 | 踏雪赤兔

抱歉……我没学过pascal啊……中学没有接触过OI…… 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2007-12-13 13:30 | isjk

貌似没构造函数，size 没初始化就开始 ++ 了回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2007-12-13 14:01 | 踏雪赤兔

呵呵~从软件工程的角度来说的确不够严谨和规范，但对于竞赛来说，因为
1、代码越短越好
2、没人会把线段树放在栈中的，全局或静态的变量会自动初始化为0。
所以我才采用了这种设计。
谢谢你的意见~^^ 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2008-03-02 16:35 | masxyja

logN时间复杂度如何计算？回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2008-03-03 10:46 | 踏雪赤兔

保证平衡的二叉树，深度最大为O(logN) 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2008-03-08 02:22 | 菜鸟

@踏雪赤兔
lower_bound()只能得到位置，如果要算前面有多少个必须逐个枚举，复杂度高达O(n)

lower_bound() - begin() 不就知道有多少个了嘛回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2008-03-08 11:42 | 踏雪赤兔

请楼上自己写个程序来检验一下……不是所有的iterator都支持operator -的~~更准确地说，是只有random_iterator才支持operator -~~ 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2008-09-11 18:59 | 小小小东西

构造了一个完全二叉树，其中叶子节点用来存放数据，树枝节点[0,N-2],叶子节点[N-1,2N-1]，叶子节点用来计数，树枝节点用来存放其右子树叶子节点的个数(类似见顺序树)。
其中若n为偶数，则n/2为其父节点，且n为其左孩子
若n为奇数，则n/2为其父节点，且n为其右孩子

空间利用率只有50%。。。。
回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2008-09-12 15:41 | 踏雪赤兔

分析得不错。纠正一下楼上一些小错误：
树枝节点是[1,N-2]，其中1是根节点
叶子节点是[N-1,2N-1]，没错。

作为平衡树，或完全二叉树，50％的额外空间似乎是免不了的，本实现相对于经典的线段树实现，少保存了很多指针，因此在对空间利用上是大有提高的。
回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2009-03-20 20:14 | LRY

据我所知，数状数组可以在logn的时间内求出第k小的数。回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2009-04-11 17:43 | 踏雪赤兔

@LRY
也许你理解的树状数组与我理解的不大一样～我的理解与百度百科解释（http://baike.baidu.com/view/1420784.htm）相同，对于这种树状数组，求第K小数是需要(logN)^2的～回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2010-04-20 21:33 | student

怎么不对
回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2010-04-20 21:34 | student

我输出了个22 1484 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2010-04-20 21:43 | student

发个完整的来 1484 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2010-05-08 16:26 | djkpengjun

我恨你回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2010-07-13 00:27 | Arios

其实树状数组也可以logn求第k小元素的，只不过麻烦些。从树高最高的点出发，然后沿着其子节点按树高从高到低比较判断就可以了，不过代码实现跟没有博主的点树实现那么简洁了~
真的非常膜拜可以自己设计数据结构的~博主这几个简单的函数我看了好久好久了~学习了，呵呵~ 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2010-08-19 08:57 | Yip

如果有pascal代码就更好了！回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2010-12-01 20:09 | LSK

其实LZ，树状数组用二分也能求第K小（大）元素的回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2010-12-08 09:01 | 魏羿容

@踏雪赤兔我也想問妳啊，這個是幹嗎用的啊：
for (;i > 1 ; i /= 2 )
if ( ~ i & 1 ) a[i/ 2] ++ ;
for (; i > 1 ; i /= 2 )
if (i & 1 ) c += a[i / 2 ];
還有啊為什么要a[N*2]最大數不是N？
有沒有點樹的圖啊？來一副更好理解啊！謝謝大牛指導拉！！回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2010-12-08 15:17 | acumon

@魏羿容
不好意思，我最近比较忙，你试试自己画一下吧，很简单的。回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2010-12-09 10:43 | 魏羿容

那跟我i说说这个的含义，我主要这个看不懂，其他的好办
：for (;i > 1 ; i /= 2 )
if ( ~ i & 1 ) a[i/ 2] ++ ;
for (; i > 1 ; i /= 2 )
if (i & 1 ) c += a[i / 2 ];
谢谢啦点拨下就通了回复更多评论

# 树状数组可以logn找第k大

2011-03-13 09:12 | BITlover

树状数组可以logn找第k大. 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2011-04-07 23:36 | yy17yy

膜拜一下回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2011-04-07 23:49 | yy17yy

首先是楼主的无比的敬仰,,,不过这个点树,,个人认为,,意义不大,,,

首先点树能实现的,,线段树都可以做,,唯一的优势是代码量稍少,,

然后是空间复杂度,,,O(n*2)是不对的吧,,,应该是O(n*3)的,,因为你这个就比线段树少存了一个原数组(你的n必须是2的k次方),,而树状数组是O(n)的,而不是O(n*2),,,

然后是时间复杂度,,,你这个因为是二叉树,,所以是严格的logn的,和线段树一样,,(应该比线段树稍快吧),,而树状数组的平均复杂度是小于logn的,,所谓我们常说的树状数组的常数低,,,因为它不是二叉树,,可以看百度百科的图..

所以树状数组确实可以独立于线段树之外存在,,而你这个结构的意义便没有那么大了...

另外觉得树状数组的求和的本质就是类似自顶向下的,,只是没有那么强的功能,,我也认为树状数组理论上可以实现线段树的所有功能,包括lazy思想,,,只是写起来要比线段树困难的多,,方法是用和线段树一样的递归的方式...

个人愚见,,,,, 回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2011-07-12 00:02 | 路人甲

我怎么觉得这个是带有标记的完全二叉的二叉查找树啊。。。
每个节点多加了一个标记用于表示左子树的点数。。。
是我没文化了么。。。回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2011-08-03 12:30 | fremn

从 barty大神空间过来。其实没必要，和普通线段树差不多回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2011-11-06 16:45 | guses

耳温枪 @魏羿容
回复更多评论

# re: 线段树的一种简化实现[原] by 踏雪赤兔

2013-05-30 14:48 | huganle

楼主请教一下，为啥N必须是2的幂次？想了好长时间没想明白回复更多评论