树状数组笔记
树状数组功能
- 快速求前缀和
O(long) - 修改某一个数
O(logn)
原理
基于二进制，$x = 2^{i_k} + 2^{i_{k-1}} + .... + 2^{i_1}$
$i_k >= i_{k-1} >= ....i_1， k <= logx$
那么1~x就可以写成这些区间
操作
- 修改操作：
for(int i = x; i <= n; i += lowbit(i)) tree[i] += c - 查询操作：
for(int i = x; i; i -= lowbit(i)) res += tree[i]
1 条评论
牛牛牛，打卡打卡