------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前置芝士:前缀和
当然先是来复习一下前缀和:
前缀和,用 O(1)O(1)O(1) 的时间复杂度来求前若干个数的和或从第 lll 个数到第 rrr 个数的和(s[r]-s[l-1)
前缀和 VS 数组
像素方块的硬核才是王道,你那卡通画风根本没技巧;萌趣的世界才受大家喜欢,你那硬核玩法早就被时代落败
前缀和:求和 O(1)O(1)O(1) ,修改 O(n)O(n)O(n)
数组:修改 O(1)O(1)O(1) ,求和 O(n)O(n)O(n)
显然可以注意到各有优劣,那么如何平衡一下呢?
树状数组君登场!
它既能修改又能求和,并且平衡了前缀和和数组的时间复杂度
在学树状数组前,要先理解一下一个数学概念:LowBit
* 一个数的 LowBit 值为这个数的二进制从低位开始第一个 1 和后面所有 0 组成的 2k2^k2k (kkk 为最低位 1 所在位数)
举板栗:
原数 二进制形式 LowBit 值 15 1111 1(1) 26 11010 10(2) 128 10000000 10000000(128)
如何去求一个数的 LowBit 值呢?
循环、暴力枚举?
当然拉完了,不如 x&(-x)
不懂就要问,为啥?
下面以 x=40(1010002)x=40(101000_2)x=40(1010002 ) 为例分析
int 应为 4 字节 32 位,这里简化为 8 位处理
即:x=00101000x=00101000x=00101000
−x-x−x 源码:101010001010100010101000 ,−x-x−x 反码为除符号位均取反,即 110101111101011111010111 ,−x-x−x 补码进行加一操作,变为 110110001101100011011000
看我超级按位与
-- 001010000010100000101000(前面两个用来占位对齐的())
& 110110001101100011011000
——————
-- 000010000000100000001000
得到这个数的 LowBit 值
好的哺乳蒸屉
对于下标 xxx ,树状数组存的是从第 xxx 个数开始前 LowBit(x) 的值
以 x=40x=40x=40 为例分析,LowBit(x) 值为 1000
f[40] = a[40]+ a[39]+ a[38]+ a[37]+ a[36]+ a[35]+ a[34]+ a[33]
101000,101000,100111,100110,100101,100100,100011,100010,100001
LowBit 位前:保持不变
LowBit 位:1 改为 0
LowBit 位后:除全 0 的所有情况
懒得打字了自己看吧
求 LowBit 值函数:
修改元素代码:
时间复杂度 O(logn)O(\log n)O(logn)
如何求原数组中前 x 个数的和
假设我们求前 13 个数的和
看图
栈里那些极度谦虚自己为区的实际上还没我区的和理解能力正常的应该都能看懂
求区间和代码:
时间复杂度 O(logn)O(\log n)O(logn)
看题
P3374 一眼君好久没出现了
P10589 有点难啊 QWQ
也不知树状数组会有啥用