树状数组

树状数组

lowbit()

lowbit(x)是x的二进制表达式中最低位的1所对应的值(即返回x二进制为一的最低位数值)。

lowbit(0)=0

常用写法:

int lowbit(int x){
	return x&(-x);
}
//利用了负整数的补码特性

用法

维护区间

设节点编号为x,那么该节点维护的区间和是 $ ( x - lowbit ( x ) , x ] $ 。

树状数组

基本操作复杂度: $ O ( logn ) $

树状数组利用了lowbit()来进行区间维护。

令父节点储存其子节点之和,

则不难发现:

$ C [ i ] = A [ i - 2k + 1 ] + A [ i - 2k + 2 ] + ...... A [ i ] $

(k为i的二进制中从最低位到高位连续零的长度)

lowbit(x) 就是取出x的最低位1,换言之lowbit(x)=2k, k的含义与上面相同,所以:

$ C [ i ] = A [ i - lowbit ( i ) + 1 ] + A [ i - lowbit ( i ) + 2 ] + ...... A [ i ] $

主要性质

性质1

每个内部结点 $ C [ x ] $ 保存以它为根的子树中所有叶结点的和。

应用

前缀和查询

区间和查询

$ sum ( y ) - sum ( x - 1 ) $

性质2

每个内部结点 $ C [ x ] $ 的子结点个数等于其lowbit(x)的值。

性质3

除树根以外,每个内部结点 $ C [ x ] $ 的父亲结点是 $ C [ x + lowbit ( x ) ] $

应用

单点修改

性质4

树的深度为 $ O ( logn ) $ 。

注意

树状数组只能处理下标为1...n的数组,绝不能出现下标为0的情况。因为lowbit(0)=0,会陷入死循环。

拓展

一维树状数组的每个操作都是 $ O ( logn ) $ ,它可扩展到m维,复杂度变成 $ O ( log^m n ) $

扩展方法

将原来的修改和查询函数中的一个循环,改成m个循环(m维数组c中的操作),以二维为例:

并非原创,仅是整理,请见谅

原文地址:https://www.cnblogs.com/audrey-hall/archive/2022/05/24/16304958.html