RMQ && 树状数组 （初学）

先复习一下今天刚学的RMQ算法知识;

RMQ算法（Range Minimum Query）

:1.算法思想

         求静态范围最值问题，适合于静态连续区间查询。
          A[ i ] [ j ] 的值代表的是原数组中以 i 开始的连续 （1<< j）个数的最值。

2.代码

<pre name="code" class="cpp">//2.1   预处理代码

for(int j = 1 ; j != 20 ; ++j )  // 代表区间大小
    for(int i = 1 ; i + (1<<j) - 1 <= n ; ++i ) // 所求区间为 [ i ,i+(1<<j)-1 ]
        Max[ i ] [ j ] = max(Max[ i ][ j-1 ] ,Max[ i + (1<<(j-1)) ][ j-1 ] )  ;
//max{ [ i ,i + (1<<(j-1)) -1 ] ,[ i + (1<<( j-1 )) , i + (1<<j) -1 ] }
//2.2    查询代码（所求区间为【x , y 】）

int  k = ( int )( log(y - x + 1.0) / log(2.0))  ;
return max( Max[ x ][ k ] , Max[ y - ( 1<<k ) + 1 ][ k ] )  ;
//     max{  [ x , x + (1<<k) -1 ] , [ y - (1<<k) + 1 , y ]

基本操作：

预备函数

定义一个Lowbit函数，返回参数转为二进制后,最后一个1的位置所代表的数值.例如,Lowbit(34)的返回值将是2；而Lowbit(12)返回4；Lowbit(8)返回8。将34转为二进制,为0010 0010,这里的"最后一个1"指的是从2^0位往前数,见到的第一个1,也就是2^1位上的1.程序上，((Not I)+1) And I表明了最后一位1的值,仍然以34为例,Not 0010 0010的结果是 1101 1101(221),加一后为 1101 1110(222), 把 0010 0010与1101 1110作AND,得0000 0010(2)

.Lowbit的一个简便求法:（C++）

：

int lowbit(int x)
{
    return x&(-x);
}

  x 的二进制中从低位往高位的第一个 1所代表的十进制数字
    lowbit( x )  = x & (-x) ;
    数字在计算机里存储的形式是二进制的补码形式，-x 的存储是把 x 的二进制除符号位外全部取反，然后加1 ，加 1 操作就实现了保留了上面提到的 x 的二进制中从低位往高位的第一个1所形成的十进制数字。（解释整数范围 (- 2^15 ~ 2^15 -1)）
Q:为什么用 lowbit()   ? 看完下面就明白了。。。
A:y = lowbit( x ) 得到的数就是 A[x] 的管辖范围指从 x 开始向后 y内的数都归 A[ x ] 管辖 。（这里可以这样理解：把A[ x ] 包含的所有的数记为此A[x] 的儿子，of course A[x] 就是所有儿子的父亲了）
具体操作：
3.  插点问线(  树状图，以公司管理为例见下页 )
       每个元素的值代表所管辖区间的值的和 。
3.1  修改某个元素的值
         当修改某个元素的值的时候必须修改所有包含他的所有的区间（即：所有的祖先），其实是分层次修改的，先修改父亲，然后修改父亲的父亲，一直修改到数组的边界。
3.2  查询某个区间的所有元素的和
      当需要计算某个区间的所有元素的和的时候，我们就可以用sum( n ) - sum(m - 1) ,这样就计算出了 m 到 n 的区间内所有元素的和。求sum( n ) 其实就是把求组成 n 的整数的区间的和（这里的整数均指2的指数级的）。
树状数组讲解图

.插线问点 （以公司发工资为例）
          元素的值代表的是所管辖区间内单个元素的值（即：每个元素的取值）
   4.1 修改区间值
           修改某个区间的值需要向下修改（见下图）。

查询某点值  
        查询本身及所有祖先的值。

复杂度log( n )
    计算sum[ n ] 实际上是不断消除 n 的二进制中最后一个 1 ，这样 n 的二进制中最多有log ( n ) 个 1 （修改最多修改log( n )个点），所以每次操作的复杂度都是log( n )的，因此预处理的时间为 nlog(n) ,有n个元素，每个元素所用的时间为log(n) ，所以预处理的总时间为 nlog(n) .