Posted on 2011-03-19 21:59
Mato_No1 阅读(1293)
评论(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了）