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了)