当前位置: 首页 > news >正文

树状数组记录

树状数组(Fenwick Tree)是一种用于维护数组前缀和的数据结构,支持高效的单点更新和区间查询操作。它的查询和更新时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn),适用于需要频繁更新和查询的场景。

树状数组的基本操作

  1. 单点更新:将数组中的某个元素增加一个值。
  2. 前缀和查询:查询数组从起点到某个位置的元素和。

树状数组的实现步骤

  1. 初始化:创建一个大小为 (n+1) 的数组 tree,初始值为 0。
  2. 单点更新:更新数组中的某个元素,并相应地更新树状数组。
  3. 前缀和查询:计算从起点到某个位置的元素和。

以区间和问题举例:


我们有一个数组,即图片中最下面一行的数组,我们也可以理解为,最下面一层是长度为1的区间,倒数第二层是长度为2的区间,然后是长度为4的区间,以此类推,并且区间不重叠。

这个图片展示出来的就是一颗线段树,树状数组是线段树的升级版。我们发现,每一个子树的右半部分可以省略不用。例如要查询[1,3]的区间和,可以通过14+1,而不用通过8+6+1,因此我们可以优化这棵树,得到:
在这里插入图片描述
到了这里,树状数组的组成结构基本就结束了,但是这样组织后,怎么确定节点之间的关系?这就要用到lowbit,这是一个十分巧妙的概念。
在这里插入图片描述
将剩下的元素组成一个数组后,我们发现,数组每一个位置索引对应的lowbit,就代表了这个位置存储的区间长度。例如我们观察61这个数,索引是16(树状数组索引从1开始),16的lowbit是16(10000->10000),代表61是区间长度为16的区间和,即[1,16],同理,3的索引是9,9的lowbit是1(1001->1),代表9是区间长度为1 [9,9]的区间和。

查询是向前查询

有了这个概念后,查询和更新就很明显了,如果要查询区间[l,r],我们可以查询[0,r]-[0,l],查询方式是:递归减去lowbit,累计数组元素的和,例如计算[1,3],我们先得到索引为3的数值1,然后更新位置 3-lowbit(3)=2,然后从2开始得到14,2-lowbit(2)=0,结束递归,结果为1+14=15。

更新是向后更新

对于更新树状数组的元素,我们需要修改每一个包含了这个元素的所有区间。
与查询不同,修改需要向后修改。如果修改了索引为9的3,我们需要修改9,10,12,16存储的内容。我们发现,与查询相似,可以通过+lowbit来得到包含自己的更大的区间,例如:9+lowbit(9)=10, 10+lowbit(10)=12, 12+lowbit(12) = 16,因此我们同样使用递归,直到索引到达数组长度上限。

区间异或问题

#include<bits/stdc++.h>using namespace std;typedef long long ll;int t[300005];
int a[300005];
int n, q;inline int lowbit(int x) {return x & -x;
}int get(int x) {int res = 0;for (int i = x; i; i -= lowbit(i)) {res ^= t[i];}return res;
}void add(int x, int y) {for (int i = x; i <= n; i += lowbit(i)) {t[i] ^= y;}
}int range_get(int l, int r) {return get(r) ^ get(l - 1);
}int main(){cin >> n >> q;for(int i = 1; i <= n; i++){cin >> a[i];add(i, a[i]);}while(q--){int op, x, y;cin >> op >> x >> y;if(op == 1){add(x, y);}else{cout << range_get(x, y) << endl;}}
}

相关文章:

树状数组记录

树状数组&#xff08;Fenwick Tree&#xff09;是一种用于维护数组前缀和的数据结构&#xff0c;支持高效的单点更新和区间查询操作。它的查询和更新时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)&#xff0c;适用于需要频繁更新和查询的场景。 树状数组的基本操作 单点更…...

客户端时间和服务器时间的区别

客户端时间&#xff1a; 服务器向客户端拷贝一份前端内容&#xff0c;客户端通过JS获取时间&#xff0c;这样获取的是客户端时间 服务器时间&#xff1a; 服务器通过java代码获取的时间传输给客户端&#xff0c;这样获取的是服务器时间 当有些时候需要使用客户端时间&#xf…...

已入职华为!!关于我成功拿下华为大模型算法岗经验总结

方向:大模型算法工程师 整个面试持续了1小时10分钟&#xff0c;能够看出面试官是典型搞技术的&#xff0c;问的很专业又很细&#xff0c;全程感觉压力好大&#xff0c;面完后感觉丝丝凉意&#xff0c;不过幸好还是成功拿下了Offer 一面: 自我介绍 简历项目深度交流 1.项目的背…...

从安卓开发到AI产品经理——我的AI绘画之旅

大家好&#xff0c;我是一名有着多年安卓开发经验的程序员。在日复一日的编码生活中&#xff0c;我对AI行业产生了浓厚的兴趣。于是&#xff0c;我决定转行成为一名AI产品经理。在这个过程中&#xff0c;我通过学习AI绘画工具初步了解了AI行业&#xff0c;下面我将分享我的学习…...

代码随想录八股训练营第三十四天| C++

前言 一、vector和list的区别&#xff1f; 1.1.存储方式&#xff1a; 1.2.随机访问&#xff1a; 1.3.插入和删除操作&#xff1a; 1.4.内存使用&#xff1a; 1.5.容量和大小&#xff1a; 1.6.迭代器类型&#xff1a; 1.7.用途&#xff1a; 二、vector 底层原理和扩容过…...

《深入理解 Java 中的 this 关键字》

目录 一、this关键字的基本理解 二、this调用属性和方法 &#xff08;一&#xff09;一般情况 &#xff08;二&#xff09;特殊情况 三、this调用构造器 四、案例分析 &#xff08;一&#xff09;Account类 &#xff08;二&#xff09;Customer类 &#xff08;三&…...

python文件自动分类(5)

完成了文件自动分类的操作后&#xff0c;我们一起来复习下&#xff1a; 首先&#xff0c;获取文件夹中所有文件名称&#xff0c;用 os.path.join() 函数拼接出要移动到的目标地址。然后&#xff0c;使用 os.path.exists() 函数判断目标文件夹是否存在&#xff0c;不存在用 os.m…...

【Unity-Lua】音乐播放器循环滚动播放音乐名

前言&#xff1a;Unity中UI节点 图1 如上所示&#xff0c;一开始本来是打算用ScrollView做的&#xff0c;觉得直接计算对应的文本位置就行&#xff0c;所以没用ScrollRect来做&#xff0c;可以忽略Scroll&#xff0c;Viewport这些名字。如下图&#xff1a;需要在一个背景Image…...

宏碁扩展Swift系列,推出四款全新AI笔记本电脑

Acer正在扩展其Swift笔记本产品线&#xff0c;推出四款新型号&#xff0c;每款都内置了AI功能。这些笔记本提供诸如Microsoft Copilot、Acer用户感应技术、Windows Studio效应、PurifiedVoice 2.0和PurifiedView等功能。其他功能还包括Wi-Fi 7和Bluetooth 5.4连接。 我们先来看…...

科研绘图系列:R语言差异基因四分图(Quad plot)

文章目录 介绍加载R包导入数据数据预处理画图参考介绍 四分图(Quad plot)是一种数据可视化技术,通常用于展示四个变量之间的关系。它由四个子图组成,每个子图都显示两个变量之间的关系。四分图的布局通常是2x2的网格,每个格子代表一个变量对的散点图。 在四分图中,通常…...

文字或图案点选坐标点返回

最近看到这篇文章中讲到极验图片验证码破解方案 https://blog.geetest.com/article/65aaaa944edc5ec343ba9f52efef0cdc 其中核心解决步骤如下&#xff0c;作者还贴心的贴出了CNN代码&#xff0c;真是用心良极&#xff1a; step 3&#xff1a;批量下载存储验证图片&#xff0c;…...

硬盘数据恢复软件TOP4榜单出炉,选对方法竟然如此重要

这年头&#xff0c;信息多得不得了&#xff0c;数据对我们来说太重要了。但是&#xff0c;不管是咱们自己还是公司&#xff0c;都可能碰上丢数据的倒霉事&#xff0c;特别是不小心把硬盘里的东西删了。数据一丢&#xff0c;不光可能亏钱&#xff0c;工作和生活也可能受影响。好…...

给自己复盘用的随想录笔记-栈与队列

用栈实现队列 难在出去 232. 用栈实现队列 - 力扣&#xff08;LeetCode&#xff09; class MyQueue {private Stack<Integer> A;private Stack<Integer> B;public MyQueue() {Anew Stack<>();Bnew Stack<>();}public void push(int x) {A.push(x);}pu…...

微信小程序跳转到另一个微信小程序

引用&#xff1a;http://www.xmdeal.com/mobanjiaocheng/254.html 第一种方法&#xff1a; wx.navigateToMiniProgram 官方文档&#xff1a;https://developers.weixin.qq.com/miniprogram/dev/api/navigate/wx.navigateToMiniProgram.html wx.navigateToMiniProgram({appId…...

【知识图谱】4、LLM大模型结合neo4j图数据库实现AI问答的功能

昨天写了一篇文章&#xff0c;使用fastapi直接操作neo4j图数据库插入数据的例子&#xff0c; 本文实现LLM大模型结合neo4j图数据库实现AI问答功能。 废话不多说&#xff0c;先上代码 import gradio as gr from fastapi import FastAPI, HTTPException, Request from pydantic…...

《信息技术 云计算 边缘云通用技术要求》国家标准发布,九州未来参编

日前&#xff0c;2024年第17号国家标准公告发布&#xff0c;由全国信标委云计算标准工作组组织制定、九州未来作为行业专家单位参编的《信息技术 云计算 边缘云通用技术要求》国家标准正式获批发布。 边缘云作为云计算技术的有效补充和拓展&#xff0c;能够实现将云计算能力拓展…...

NTFS硬盘支持工具Paragon NTFS for Mac 15.4.44 中文破解版

Paragon NTFS for Mac 15.4.44 中文破解版是一个底层的文件系统驱动程序,专门开发用来弥合Windows和Mac OS X之间的不兼容性&#xff0c;通过在Mac OS X系统下提供对任何版本的NTFS文件系统完全的读写访问服务来弥合这种不兼容性。为您轻松解决Mac不能识别Windows NTFS文件难题…...

66-java 类型擦除

类型擦除是Java类型信息在运行时的一个特性&#xff0c;它发生在泛型类型被擦除成它们的原始类型后&#xff0c;以及在运行时&#xff0c;由于类型擦除&#xff0c;泛型信息不可用。 例如&#xff0c;以下两个泛型类型&#xff1a; List<String> list1 new ArrayList&…...

25考研人数预计下降?这一届考研有哪些新趋势?

2025年考研时间线&#xff1a; 2024年9月&#xff1a;公共课及各院校考试大纲公布&#xff1b; 2024年9月下旬&#xff1a;预报名&#xff1b; 2024年10月&#xff1a;正式报名&#xff1b; 2024年11月&#xff1a;线上/线下确认&#xff1b; 2024年12月中下旬&#xff1a…...

比尔·盖茨对AI充满信心

The Verge与比尔盖茨进行了关于AI、错误信息和气候变化的对话。 比尔盖茨花费数十亿美元资助他认为将塑造未来的技术——从应对气候变化到消灭疾病。 盖茨在一部新的Netflix系列片《未来之路&#xff1a;比尔盖茨的境界》中深入探讨了这些话题。该系列于9月18日首播&#xff…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建

制造业采购供应链管理是企业运营的核心环节&#xff0c;供应链协同管理在供应链上下游企业之间建立紧密的合作关系&#xff0c;通过信息共享、资源整合、业务协同等方式&#xff0c;实现供应链的全面管理和优化&#xff0c;提高供应链的效率和透明度&#xff0c;降低供应链的成…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

GitFlow 工作模式(详解)

今天再学项目的过程中遇到使用gitflow模式管理代码&#xff0c;因此进行学习并且发布关于gitflow的一些思考 Git与GitFlow模式 我们在写代码的时候通常会进行网上保存&#xff0c;无论是github还是gittee&#xff0c;都是一种基于git去保存代码的形式&#xff0c;这样保存代码…...