Loading... # 树状数组笔记 ## 树状数组功能 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 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏
1 条评论
牛牛牛,打卡打卡