2352-2299-3067.pdf

树状数组／线段树 数据结构的引入与讨论 树状数组部分 ——杨挺 引入 Example: 给出一数列： A[ 1 ]、A[ 2 ]、A[ 3 ]……A[ n ] 对其有两种操作： Add  ij : A[ i] = A[ i] + j； Sum ij : 询问A[ i]至A[ j ]的和并输出。 共有m次操作。 思路一 Add  i j :  以O( 1 )的时间A[ i ] += j； Sum i j :  以O( n )的时间累加出结果。 总时间复杂度为O( n * m )。 Time Limit Exceeded ！！！ 思路二 增开S数组：S[ i ]表示从A[ 1 ]到A[ i ]之和； Sum i j :  O( 1 )时间求出，即ans = S[ j ] –S[ i –1 ]； Add  I j :  O( n )时间，对于A[ i ]修改，必须更新S[ i ]至 S[ n ]的值。 复杂度仍为O( n * m )。 时间就是生命！！！ 急需引进一种修改与查询耗时相对较少的数据结构 ——树状数组即为所求 Lowbit函数 lowbit函数： 表示二进制中最后一个不为零的位。 如： lowbit( (10100) ) = (100) ； 2 2 lowbit( (10010) ) = (  10) 。 2 2 可得出： lowbit( X ) = X  ( X ^ ( X –1 ) )； ※根据机器补码的性质还可以得出： lowbit( X ) = X  ( –X )。 树状数组 定义： 若A为原数组，定义数组C为树状数组。 C数组中元素C[ i ]表示A[ i –lowbit( i ) + 1] 至A[ i ]的结合值。 ※结合值：满足结合律的交运算结果。 如： 求和则为这一段的和； 求最优值，则表示这一段的最优值。 树状数组 此图中结合值即为元素之和： C[ 1 ] = A[ 1 ]； C[ 2 ] = A[ 1 ] + A[ 2 ]； C[ 3 ] = A[ 3 ]； C[ 4 ] = A[ 1 ] + A[ 2 ] + A[ 3 ] + A[ 4 ]； C[ 5 ] = A[ 5 ]； C[ 6 ] = A[ 5 ] + A[ 6 ]； C[ 7 ] = A[ 7 ]； C[ 8 ] = A[ 1 ] + A[ 2 ] + A[ 3 ] + A[ 4 ] + A[ 5 ] + A[ 6 ] + A[ 7 ] +  A[ 8 ]； …… 树状数组支持的操作 更新最优值（improve操作） 引理1：若对A[ k ]值有修改（权值不变坏）， 设它影响的C数组为C[ p ]、C[ p ]……C[ p ]， 1 2 m 则p = k；p = p+ lowbit( p )。 1  i+1  i  i Void improve( int k ) { for ( int j = k; j = n; j += lowbit( j ) )  C[ j ]