树状数组 (二元索引树 / 二元下标树 / Binary Indexed Tree, BIT / Fenwick Tree): 树状数组虽名为数组,但从其英文名 (Binary Indexed Tree) 可看出它本质上是一种被表达为树的数据结构。对于大小为n 的序列nums ,最基本的树状数组以O(logn) 时间复杂度同时支持如下两种操作。
1)更新nums 中单个元素的值,即 单点修改(Point Update) 。
2)求nums 任意区间的元素值之和,即 区间查询(Range Query) 。
数组:对于单点修改:数组可以利用下标直接修改,O(1),但是对于区间查询则为O(N);
前缀和:对于区间查询,前缀和可以做到O(1),但是对于单点修改,需要修改该点以后的所有前缀和数值,O(N);
学习视频摘自:〔manim | 算法 | 数据结构〕 完全理解并深入应用树状数组 | 支持多种动态维护区间操作_哔哩哔哩_bilibili
学习博客摘自:树状数组从入门到下车 - 力扣(LeetCode)
lowbit操作:
t [ ] 数组:
单点修改、区间查询:
区间修改、单点查询:
区间修改、区间查询:
整个矩形面积,减去黄色面积;
注意这儿是 前缀和的增量;
标签:单点,树状,--,查询,修改,数组,区间 From: https://www.cnblogs.com/xuan01/p/17395537.html