树状数组基本操作_树状数组两个操作-程序员宅基地

一维树状数组

如果我们想实现求前缀和和修改某一个数的操作，用普通数组来做时间复杂度分别是 O(n) 和 O(1),但如果用树状数组来做时间复杂度都为log(n),降低了整体时间复杂度。

通过上图下方的设计，可以在log(n)时间内求出前缀和。

树状数组有两个核心的操作：

void add(int x, int c)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

第一个操作为单点修改，第二个操作为单点查询

难道树状数组只能支持这两个操作吗？

非也非也，通过一些技巧，树状数组能拓展出很多功能。

1.区间修改与单点查询-----差分

例题：一个简单的整数问题242. 一个简单的整数问题 - AcWing题库

假如需要修改的区间为 [ L , R ] ,则只需要维护一个差分树状数组，在 L 的位置加上需要加的数，在 R+1 的位置减去即可。

2.区间修改与区间求和----二维前缀和、差分

例题：一个简单的整数问题2243. 一个简单的整数问题2 - AcWing题库

3.剩余数中第k小的数，删除某一个数----树状数组维护“1”的前缀和+二分

如果一个数存在则记为1，原问题1转化为找出一个最小的数使得 sum [ x ] = k ,二分即可。

删除一个数则赋为0。

例题：谜一样的牛244. 谜一样的牛 - AcWing题库

二维树状数组

因为我也没学过，所以参考了其他博客。

感觉二维树状数组总结及模板_Lv1_kangdi的博客-程序员宅基地_二维树状数组将操作讲的很透彻，但是没具体说二维树状数组的含义，在数据结构——二维树状数组_星*湖的博客-程序员宅基地_二维树状数组中说，在二维树状数组中，arr[x][y] 记录的是右下角为(x,y)，高度为 lowbit(x)，宽度为 lowbit(y) 的区间和。

本文链接：https://blog.csdn.net/w75779/article/details/127131454

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

fopen,fopen_s,_wfopen_s与_fsopen, _wfsopen的区分_fopen_s和fopen的区别-程序员宅基地

文章浏览阅读1.5w次，点赞2次，收藏13次。C++做项目的过程中，需要实现文件打开保存的一个功能，当我对文件tmp.dat进行写操作以后，想要第二次对此文件进行写操作，此时用fopen_s,_wfopen_s均出现返回int error = 13也就是EACCES （Permission denied）的错误。而由于项目是Unicode编码，没办法用fopen进行文件操作（其实只要在预编译中加入_CRT_SECURE_NO_WARN_fopen_s和fopen的区别

合工大计算机组成原理ppt,合工大计算机组成原理计算机组成原理提纲.pdf-程序员宅基地

文章浏览阅读251次。合工大计算机组成原理计算机组成原理提纲计算机组成原理计算机组成原理合肥工业大学计算机与信息学院陈陈田田2013.12.12提纲11 考试形式和试卷结构考试形式和试卷结构2 考查目标3 参考书目44 考点及重点难点分析考点及重点难点分析计算机与信息学院 ..._计算机组成原理合工大

PostgreSQL--读懂执行计划(一)_postgresql 执行计划-程序员宅基地

文章浏览阅读7.9k次，点赞5次，收藏42次。这里写自定义目录标题前言执行计划常用命令参数解读常用组合执行计划解读关键字常见扫描方式Seq ScanIndex Only ScanIndex ScanBitmap Index Scan+Bitmap Heap ScanHash JoinNested LoopMerge Join小结前言PostgreSQL为每个收到查询产生一个查询计划。选择正确的计划来匹配查询结构和数据的属性对于好的性能来说绝对是最关键的，因此系统包含了一个复杂的规划器来尝试选择好的计划。你可以使用EXPLAIN命令察看规划器为任_postgresql 执行计划

释放AI创作潜能：从大模型训练到高产力应用-程序员宅基地

文章浏览阅读1.4w次，点赞83次，收藏82次。随着科技的不断进步，人工智能已经成为了各行各业的必备技能。特别是在内容创作领域，人工智能生成内容（AIGC）正逐渐成为趋势。AI可以创造出优秀的、原创的文章和故事，这为创作者们提供了一种新的创作方式。同时，AIGC技术也可以节省人力成本，提高内容生产效率。但是，如何在使用技术的前提下保持内容的原创性和质量，这是我们需要思考的问题。

mysql root 访问被拒绝_mysql-“连接失败：用户'root'@'localhost'（使用密码：是）的访问被拒绝”...-程序员宅基地

文章浏览阅读3.7k次。mysql-“连接失败：用户'root'@'localhost'(使用密码：是)的访问被拒绝”这个问题在这里已有答案：MySQL错误1045(28000)：用户'bill'@'localhost'的访问被拒绝(使用密码：是) 35个答案我写了一些PHP网页使用的函数，以便与mysql数据库进行交互。当我在服务器上测试它们时，..._mysql -uroot -p 数据库访问拒绝oot @localhost

【分布式缓存】springboot整合jetcache使用详解_springboot集成jetcache如何操作jetcache-程序员宅基地

文章浏览阅读5k次，点赞103次，收藏105次。springboot整合jetcache使用详解_springboot集成jetcache如何操作jetcache

随便推点

静态编译的方式合并第三方dll，并生成自己的dll，以及出现‘__acrt_first_block == header’异常解决方式_vs 将opencv的dll打包到自己的dll-程序员宅基地

文章浏览阅读4.7k次，点赞2次，收藏8次。有时候调用了第三方的dll，但是由于种种原因不能显示出来，需要将第三方dll封装到自己的dll里，在使用时，让别人只你的dll，而不用调用你使用的第三方dll。怎么实现？用静态编译的方式！最近由于项目需要，用VS2015+opencv2.4.13编程实现了静态编译生成自己的dll，这个dll相当于将opencv的部分功能封装到自己的dll中了（不要跟我说opencv开源，不需要封装到自己的d..._vs 将opencv的dll打包到自己的dll

unity Android安卓平台读取Application.persistentDataPath路径_unity怎么读取 application.persistentdatapath 下的文件-程序员宅基地

文章浏览阅读3.1k次。这次这么测试是对的，下次再有问题再看看写入的时候这样写的： fileLocal = Application.persistentDataPath + "/" + path; finalPath =#if UNITY_ANDROID && !UNITY_EDITOR fileLocal;#else "file://" + fileLocal;#endif读取的时候这样写的： path =#._unity怎么读取 application.persistentdatapath 下的文件

C语言数据结构栈的顺序表示和实现-程序员宅基地

文章浏览阅读2.8k次，点赞7次，收藏47次。栈的顺序表示和实现文章目录1 顺序栈结构2 基本操作函数3 整体代码test3.cStack.h4 运行结果5 附加题栈的存储结构可以是顺序表或链表，该篇为顺序表存储栈是后进先出的数据结构1 顺序栈结构栈结构体top永远指向下一个typedef struct Stack{ DataType data[maxn]; // 作为栈元素的存储方式，数据类型为DataType int top; // top即栈顶指_栈的顺序表示和实现

总结Vue中index.html、main.js、App.vue、index.js之间关系以及Vue项目加载流程_index.html 是vue 项目的-程序员宅基地

文章浏览阅读7.9k次，点赞15次，收藏105次。总结Vue中index.html、main.js、App.vue、index.js之间关系以及Vue项目加载流程文章目录总结Vue中index.html、main.js、App.vue、index.js之间关系以及Vue项目加载流程1 vue中index.html、main.js、App.vue、index.js关系简介1.1 项目的运行入口index.html1.2 入口文件main.js1.3 根组件App.vue1.4 控制路由index.js2 Vue项目加载流程1 vue中index.html_index.html 是vue 项目的

lammps数据后处理：python绘制应力应变曲线附程序代码_混凝土应力应变曲线图绘制代码-程序员宅基地

文章浏览阅读1.7k次。绘制应力应变的方法有很多，常规的做法是把数据文件拖入到origin绘图，还有一个简单的方法是使用python脚本，在模拟完成后，直接运行一下脚本就能得到应力应变曲线，可以快速的观察运行结果。_混凝土应力应变曲线图绘制代码

基础函数案例作业简易计算器(可参考做ATM取款机)代码_写一个函数,实现用户输入任意两个数字的任意算术运算(简单的计算器小功能),并能弹-程序员宅基地

文章浏览阅读760次，点赞2次，收藏3次。1、写一个函数,用户输入任意两个数字的任意算术运算(简单的计算器小功能) , 并能弹出运算后的结果。 var num1 = prompt('第一个数字：'); var num2 = prompt('第二个数字：'); function getjisuan(num1,num2){ return [parseFloat(num1) + parseFloat(num2), num1 * num2, num1 / num2]; } alert(getjisuan(num1,num2));_写一个函数,实现用户输入任意两个数字的任意算术运算(简单的计算器小功能),并能弹