树状数组笔记

树状数组功能

  1. 快速求前缀和O(long)
  2. 修改某一个数O(logn)

原理

基于二进制，$x = 2^{i_k} + 2^{i_{k-1}} + .... + 2^{i_1}$

$i_k >= i_{k-1} >= ....i_1， k <= logx$

那么1~x就可以写成这些区间

操作

  1. 修改操作：for(int i = x; i <= n; i += lowbit(i)) tree[i] += c
  2. 查询操作：for(int i = x; i; i -= lowbit(i)) res += tree[i]
最后修改：2023 年 01 月 31 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏