首页 > 其他分享 >树状数组--动态维护区间操作

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

时间:2023-05-12 20:46:38浏览次数:48  
标签:单点 树状 -- 查询 修改 数组 区间

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

相关文章

  • 团队绩效考核不被淘汰理由
    因为自己是本次团队绩效考核成绩最低的成员,故特此说明不被淘汰的理由:首先,我深刻反思自己在团队中的表现,发现自己并未时常与团队之间进行交流,总是独立出去,缺乏与团队间的交流沟通是我最大的缺点,也是此次团队绩效考核成绩最低的主要原因。在团队中,我承担了Android端全部UI......
  • ImHex
    ImHexImHex是一个开源的多平台十六进制编辑器,可以解析PE/ELF等类型文件,和010Editor功能类似,支持Windows、MacOS、Linux。官网地址:https://imhex.werwolv.net/官方文档:https://docs.werwolv.net/documentation/github地址:https://github.com/WerWolv/ImHexpattern可用来......
  • 5.12
    #include<iostream>#include<string>usingnamespacestd;classDocument{public:   Document(){   }   Document(char*nm);   char*name;   voidPrintNameOf();};Document::Document(char*nm){   name=newchar[strlen(nm)+1];......
  • hashcat
    hashcat官网:https://hashcat.net/hashcat/用来爆破各种hashUsage:hashcat[options]...hash|hashfile|hccapxfile[dictionary|mask|directory]...hash字符串或hash文件均可,掩码或字典文件均可官方提供示例:-[BasicExamples]-Attack-|Hash-|Mod......
  • SpringCloud之Zookeeper作为配置中心
    Zookeeper提供了一个分层的命名空间,让客户端可以存储任意数据,例如配置数据。SpringCloudZookeeperConfig是ConfigServer和Client的替代方案。在特殊的“bootstrap”阶段,配置被加载到Spring环境中。默认情况下,配置存储在/config命名空间中。将根据应用程序的名称和活动配置文件......
  • AIGC:虚拟世界里的自动驾驶,科技推动出行方式变革丨曼孚科技
    今年,消费者对新能源汽车的需求持续走高。5月11日,中国汽车工业协会乘用车市场信息联席会发布了一则数据,截止4月末,新能源汽车产销分别完成229.1万辆与222.2万辆,同比均增长42.8%,市场占有率达27%。这一串数字,印证了新能源汽车市场的强势增速,也体现了消费者对新能源汽车认知的提升。......
  • macos13 m1 安装 mysql8.0.32
    1、下载安装包选择MySQLCommunityServer版本MySQL::DownloadMySQLCommunityServer(ArchivedVersions)2、可视化安装选择强密码策略3、环境变量配置cat.zshrcexportPATH=$PATH:/usr/local/mysql-8.0.32-macos13-arm64/binexportPATH=$PATH:/usr/local/mysq......
  • C++
    运算符重载请定义一个分数类,拥有两个整数的私有数据成员,分别表示分子和分母(分母永远为正数,符号通过分子表示)。重载运算符加号"+",实现两个分数的相加,所得结果必须是最简分数。#include<iostream>usingnamespacestd;classScore{intx=0;//分母inty=0;//分子public:......
  • 小白月赛72
    给定一个正整数�n,求[1,�][1,n]中因子数量为奇数的正整数的个数。第一行包含一个正整数TTT (1≤T≤103)(1\leqT\leq10^3)(1≤T≤103),表示数据组数。每组数据只有一行,包含一个正整数nnn (1≤n≤4×103)(1\leqn\leq4\times10^{3})(1≤n≤4×103)输出�T行,第�i行表示第�i次询问......
  • 不被淘汰博客
    对于在这次组队任务中,我获得的评分最低,我心服口服。毕竟对于我的队友来说,我对团队做出的贡献较少,但是我在团队中也做出了一些不可或缺的贡献。首先,在前期的讨论中,我建议了手机的一些功能以及布局,这使得在初期的创作中起到了作用。然后,在之后的功能创作中,我提供了关键功能的显示......