树状数组解决离线RMQ问题

Posted on 2011-03-19 21:59 Mato_No1 阅读(1319) 评论(1)  编辑 收藏 引用 所属分类: 树状数组

树状数组与线段树不同,它只能直接支持前缀区间([1..r])或后缀区间([l..N])上的操作,而对于一般区间([l..r])上的操作则需要通过两步操作间接完成:先对[1..r]进行操作再对[1..l-1]进行反操作(如加c的反操作就是减c),对于加法操作这样可反的操作是可以,而对于求最值这样的不可反的操作(无法通过[1..r]的最值与[1..l-1]的最值得出[l..r]的最值),就没有办法了。其实,用树状数组是可以解决离线RMQ问题的,但时间复杂度不太理想(一次操作的理论时间复杂度达O((logN)^2))。

方法是(这里C[i]表示i管辖的数组结点中的最值):设r'为目前的右端点,一开始r'=r。每次找到r'管辖的数组结点中最左边的那个的下标(即r' - (r' & (-r')) + 1),设为x。若x>=l,则将C[r']与目前的最值比较、更新,再将r'设为(x-1);若x<l,则调出A[r']的值与目前最值比较、更新,然后将r'减1。如此直至r'<l为止。

本算法编程复杂度极低,但由于时间效率较低,难以适应较大范围数据(N, M>100000基本上就TLE了)

Feedback

# re: 树状数组解决离线RMQ问题  回复  更多评论   

2011-06-25 03:00 by AHdoc
用树状数组是可以解决离线RMQ问题的
但时间复杂度一次操作的理论时间复杂度不是O((logN)^2))

有NlogN的。

这个实际上是有办法的,而且可能不是c++的人还不太容易实现。
原本树状数组每一个结点是一个数字int,你可以用一个vector来存。
比如16位置你就存一个vector<int>来记录16往前1 2 4 8 16的最值。
然后你再求区间最值的时候,就可以O(logN)找到所有的区间,然后再logN次求解,用位运算写很方便的,总的时间复杂度logN。

找区间的部分大致是这样的,区间[s,t]。
从s开始不断+(i & (-i))。直到下一次增加超过t,记为s'。
从t开始不断-(i & (-i))。直到恰好和刚才s'重合,可以证明一定会和s'恰好重合。
这样就是logN个区间了,每一个区间的操作又是O(1)的。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理