最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

树状数组--动态维护区间操作-新动态

来源：博客园

树状数组 (二元索引树 / 二元下标树 / 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 [ ] 数组：

单点修改、区间查询：

区间修改、单点查询：

区间修改、区间查询：

整个矩形面积，减去黄色面积；

注意这儿是 前缀和的增量；

初始化tree 数组：

关键词：