数据结构-树状数组专题（2）

一、前言

接上回树状数组专题（1），这次主要介绍差分跟树状数组联动实现区间更新

二、我的模板

重新放了一遍，还是提一嘴，注意下标从0开始，区间左闭右开

template <typename T>
struct Fenwick {int n;std::vector<T> a;Fenwick(int n_ = 0) {init(n_);}void init(int n_) {n = n_;a.assign(n, T{});}void add(int x, const T &v) {for (int i = x + 1; i <= n; i += i & -i) {a[i - 1] = a[i - 1] + v;}}T sum(int x) {T ans{};for (int i = x; i > 0; i -= i & -i) {ans = ans + a[i - 1];}return ans;}T rangeSum(int l, int r) {return sum(r) - sum(l);}int select(const T &k) {int x = 0;T cur{};for (int i = 1 << std::__lg(n); i; i /= 2) {if (x + i <= n && cur + a[x + i - 1] <= k) {x += i;cur = cur + a[x - 1];}}return x;}
};

三、差分简介

差分实际上是前缀和的逆运算，类似于函数求微积分实际上是函数求导函数的逆运算。

因此我们可以得到一个结论

差分数组的前缀和等于原数组，原数组的前缀和就等于前缀和数组

前缀和的差分等于原数组，原数组的差分就等于差分数组

我们回忆一下前缀和是怎么来的

prefix[i] = prefix[i-1]+a[i]

那么移项可以得到

a[i] = prefix[i]-prefix[i-1]

这就是差分数组的构造方式，此时的a数组就相当于差分数组，prefix数组相当于原数组

因此就有

for(int i = 1;i <= n;++i){prefix[i] = prefix[i-1]+a[i];diff[i] = a[i]-a[i-1];
}

其中diff数组就是a数组的差分数组

区间修改

因此为了实现区间修改，如果要把[l,r]这个区间的数都加上x，那么我们可以对构造出来的差分数组做这样的两个操作：
diff[l]+=x;diff[r+1]-=x;

这时候你要单点查询左端点l的值，实际上就是对diff[1]到diff[l]求前缀和，由于我们树状数组的特性，可以在O(logn)的时间复杂度下完成求前缀和，你会发现a[l]的的确确加上了x，再依次对[l,r]中的值实验，发现确实都增加了x，从r+1开始，后面的值还是保持原状不增不减，这就达到了我们需要的效果

原理分析：

diff[1] = a[1] - a[0]

diff[2] = a[2] - a[1]

diff[3] = a[3] - a[2]

...

diff[l] = a[l] - a[l-1]

...

diff[r] = a[r] - a[r-1]

diff[r+1] = a[r+1] - a[r]

...

diff[n] = a[n] - a[n-1]

对diff[l]做前缀和实际上等价于求diff[1]+diff[2]+diff[3]+...+diff[l]

=(a[1]-a[0])+(a[2]-a[1])+(a[3]-a[2])+...+(a[l]-a[l-1])=a[l]-a[0]=a[l]

因此如果diff[l]+=x的话

整体求前缀和就等价于diff[1]+diff[2]+diff[3]+...+(diff[l]+x)

=(a[1]-a[0])+(a[2]-a[1])+(a[3]-a[2])+...+(a[l]-a[l-1]+x)=a[l]+x-a[0]=a[l]+x

同理，也可验证diff[r+1]+x的情况

这里就不过多阐述了

因此我们用两个O(1)的操作实现了区间修改，取代了暴力修改的O(n)的时间复杂度

区间查询

由于我们采用差分数组来构造的树状数组，那么我们要求原数组修改后的区间和，原本是需要对差分数组做两遍前缀和的，但是我们这里可以尝试构造出两个树状数组来实现求区间和

如果要求[l,r]的区间和，我们就需要先学会计算前缀和，假设我们要求前k个数的前缀和

那么对于差分数组diff[]来说，我们枚举出来，应该需要计算

a[1] = diff[1]

a[2] = diff[1] + diff[2]

a[3] = diff[1] + diff[2] + diff[3]

...

a[k] = diff[1] + diff[2] + diff[3] + ... + diff[k]

似乎找不到什么有用的结论，我们不妨添加一行，再将剩余位置补全

a[0] = diff[1] + diff[2] + diff[3] + ... + diff[k]

a[1] = diff[1] + diff[2] + diff[3] + ... + diff[k]

a[2] = diff[1] + diff[2] + diff[3] + ... + diff[k]

a[3] = diff[1] + diff[2] + diff[3] + ... + diff[k]

...

a[k] = diff[1] + diff[2] + diff[3] + ... + diff[k]

这时候我们发现，我们要求的a[1]到a[k]的和，就等于这个矩形的和减去红色部分的和

因此前k个数的和（前缀和）为(k+1)*fenwick1.sum(k)-fenwick2.sum(k)

fenwick1表示第一个树状数组，fenwick2表示第二个树状数组

fenwick1中保存的是数组a的差分数组diff，fenwick2中保存的是i*diff[i](1<=i<=n)

这块还是以会写代码为主

四、专题训练

4.1 星码StarryCoding P41 树状数组（区间修改）

思路

这题是树状数组区间修改的模板题，主要要会写代码

我的代码

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 2e5+5;template <typename T>
struct Fenwick {int n;std::vector<T> a;Fenwick(int n_ = 0) {init(n_);}void init(int n_) {n = n_;a.assign(n, T{});}void add(int x, const T &v) {for (int i = x + 1; i <= n; i += i & -i) {a[i - 1] = a[i - 1] + v;}}T sum(int x) {T ans{};for (int i = x; i > 0; i -= i & -i) {ans = ans + a[i - 1];}return ans;}T rangeSum(int l, int r) {return sum(r) - sum(l);}int select(const T &k) {int x = 0;T cur{};for (int i = 1 << std::__lg(n); i; i /= 2) {if (x + i <= n && cur + a[x + i - 1] <= k) {x += i;cur = cur + a[x - 1];}}return x;}
};int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n,q;std::cin >> n >> q;std::vector<i64> a(N,0),diff1(N,0),diff2(N,0);for(int i = 1;i <= n;++i) {std::cin >> a[i];diff1[i] = a[i]-a[i-1];diff2[i] = i*diff1[i];}Fenwick<i64> fenwick1(N),fenwick2(N);for(int i = 1;i <= n;++i) {fenwick1.add(i-1,diff1[i]);fenwick2.add(i-1,diff2[i]);}while(q--) {int op,l,r;i64 x;std::cin >> op >> l >> r;if(op==1) {std::cin >> x;fenwick1.add(l-1,x);fenwick2.add(l-1,l*x);fenwick1.add(r,-x);fenwick2.add(r,(r+1)*(-x));}else {i64 pre1 = fenwick1.sum(r)*(r+1)-fenwick2.sum(r);i64 pre2 = fenwick1.sum(l-1)*l-fenwick2.sum(l-1);std::cout << pre1-pre2 << '\n';}}return 0;
}

4.2 AcWing 242. 一个简单的整数问题

思路

跟上一题如出一辙，这个题还更加简单，因为只需要实现区间修改和单点查询，这就意味着我们只需要用一个树状数组就可以解决

我的代码

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 1e5+5;template <typename T>
struct Fenwick {int n;std::vector<T> a;Fenwick(int n_ = 0) {init(n_);}void init(int n_) {n = n_;a.assign(n, T{});}void add(int x, const T &v) {for (int i = x + 1; i <= n; i += i & -i) {a[i - 1] = a[i - 1] + v;}}T sum(int x) {T ans{};for (int i = x; i > 0; i -= i & -i) {ans = ans + a[i - 1];}return ans;}T rangeSum(int l, int r) {return sum(r) - sum(l);}int select(const T &k) {int x = 0;T cur{};for (int i = 1 << std::__lg(n); i; i /= 2) {if (x + i <= n && cur + a[x + i - 1] <= k) {x += i;cur = cur + a[x - 1];}}return x;}
};int main(){std::cin.tie(nullptr)->sync_with_stdio(false);int n,m;std::cin >> n >> m;std::vector<int> a(N,0);for(int i = 1;i <= n;++i){std::cin >> a[i];}std::vector<int> diff(N,0);for(int i = 1;i <= n;++i){diff[i] = a[i] - a[i-1];}Fenwick<int> fenwick(N);for(int i = 1;i <= n;++i){fenwick.add(i-1,diff[i]);}while(m--){std::string op;int l,r,d,x;std::cin >> op;if(op=="Q"){std::cin >> x;int ans = fenwick.sum(x);std::cout << ans << '\n';}else{std::cin >> l >> r >> d;fenwick.add(l-1,d);fenwick.add(r,-d);}}return 0;
}

4.3 AcWing 243. 一个简单的整数问题2

思路

跟4.1换个题目场景罢了，解题思路一模一样，甚至代码改几个地方就能拿过来AC掉

我的代码

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 1e5+5;template <typename T>
struct Fenwick {int n;std::vector<T> a;Fenwick(int n_ = 0) {init(n_);}void init(int n_) {n = n_;a.assign(n, T{});}void add(int x, const T &v) {for (int i = x + 1; i <= n; i += i & -i) {a[i - 1] = a[i - 1] + v;}}T sum(int x) {T ans{};for (int i = x; i > 0; i -= i & -i) {ans = ans + a[i - 1];}return ans;}T rangeSum(int l, int r) {return sum(r) - sum(l);}int select(const T &k) {int x = 0;T cur{};for (int i = 1 << std::__lg(n); i; i /= 2) {if (x + i <= n && cur + a[x + i - 1] <= k) {x += i;cur = cur + a[x - 1];}}return x;}
};int main() {std::cin.tie(nullptr)->sync_with_stdio(false);int n,m;std::cin >> n >> m;std::vector<i64> a(N,0),diff1(N,0),diff2(N,0);Fenwick<i64> fenwick1(N),fenwick2(N);for(int i = 1;i<=n;++i) {std::cin >> a[i];diff1[i] = a[i]-a[i-1];diff2[i] = i*diff1[i];}for(int i = 1;i<=n;++i) {fenwick1.add(i-1,diff1[i]);fenwick2.add(i-1,diff2[i]);}while(m--) {std::string op;int l,r;i64 d;std::cin >> op;if(op=="C") {std::cin >> l >> r >> d;fenwick1.add(l-1,d);fenwick2.add(l-1,l*d);fenwick1.add(r,-d);fenwick2.add(r,(r+1)*(-d));}else {//op=="Q"std::cin >> l >> r;i64 pre1 = fenwick1.sum(r)*(r+1)-fenwick2.sum(r);i64 pre2 = fenwick1.sum(l-1)*l-fenwick2.sum(l-1);std::cout << pre1-pre2 << '\n';}}return 0;
}

五、后记

等这几天回去再去看看线段树，后续可以类比一下线段树的写法和思路，线段树实际上更加全能，但是代码量真的太大，理解不透彻的人写着写着就Segment Fault了

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/476654.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

使用 PyTorch-BigGraph 构建和部署大规模图嵌入的完整教程

使用 PyTorch-BigGraph 构建和部署大规模图嵌入的完整教程

当涉及到图数据时&#xff0c;复杂性是不可避免的。无论是社交网络中的庞大互联关系、像 Freebase 这样的知识图谱&#xff0c;还是推荐引擎中海量的数据量&#xff0c;处理如此规模的图数据都充满挑战。 尤其是当目标是生成能够准确捕捉这些关系本质的嵌入表示时&#xff0c;…
阅读更多...
启动前后端分离项目笔记

启动前后端分离项目笔记

一、项目 首先可以在各大开源软件拿取一个项目&#xff0c;以下项目是在gitee上获取 二、准备工作 配置JDK环境&#xff0c;node.js环境&#xff0c;安装vue脚手架工具以及maven环境 三、前端项目启动 在前端目录下安装依赖 npm install 如果报错可能是因为权限不够&#…
阅读更多...
3个月，2000+台虚机迁移成功！

3个月，2000+台虚机迁移成功！

在全球数字化浪潮的推动下&#xff0c;各国政务部门纷纷加速信息化与数字化转型&#xff0c;以提升服务效率和数据安全。在这一背景下&#xff0c;墨西哥某政府部门因迅速增长的政务数字化需求&#xff0c;选择与华为云合作&#xff0c;构建专属的政务私有云平台。 经过多方尝…
阅读更多...
GRU (门控循环单元 - 基于RNN - 简化LSTM又快又好 - 体现注意力的思想) + 代码实现 —— 笔记3.5《动手学深度学习》

GRU (门控循环单元 - 基于RNN - 简化LSTM又快又好 - 体现注意力的思想) + 代码实现 —— 笔记3.5《动手学深度学习》

目录 0. 前言 1. 门控隐状态 1.1 重置门和更新门 1.2 候选隐状态 1.3 隐状态 2. 从零开始实现 2.1 初始化模型参数 2.2 定义模型 2.3 训练与预测 3 简洁实现 4. 小结 0. 前言 课程全部代码&#xff08;pytorch版&#xff09;已上传到附件看懂上一篇RNN的所有细节&am…
阅读更多...
微知-plantuml常用语法和要点以及模板？（note over、create、box,endbox、alt,else,end, autonumber）

微知-plantuml常用语法和要点以及模板？（note over、create、box,endbox、alt,else,end, autonumber）

文章目录 常见语法常用 线条类实线虚线斜箭头或奇数箭头 A ->(10) B: B->(10) A分割线&#xff1a;newpage 颜色类给箭头指定颜色 -[#red]->给某个note加颜色&#xff1a; note over Alice, Bob #FFAAAA: xxx给分组信息着色 alt#red 分组类alt xxx; else xxx; else xx…
阅读更多...
YOLOV5/rknn生成可执行文件部署在RK3568上

YOLOV5/rknn生成可执行文件部署在RK3568上

接上一篇文章best-sim.rknn模型生成好后&#xff0c;我们要将其转换成可执行文件运行在RK3568上&#xff0c;这一步需要在rknpu上进行&#xff0c;在强调一遍&#xff01;&#xff01;rknpu的作用是可以直接生成在开发板上运行的程序 退出上一步的docker环境 exit1.复制best-…
阅读更多...
2024信创数据库TOP30之蚂蚁集团OceanBase

2024信创数据库TOP30之蚂蚁集团OceanBase

数据库作为存储、管理和分析这些数据的关键工具&#xff0c;其地位自然不言而喻。随着信息技术的日新月异&#xff0c;数据库技术也在不断演进&#xff0c;以满足日益复杂多变的市场需求。近日&#xff0c;备受瞩目的“2024信创数据库TOP30”榜单由DBC联合CIW/CIS权威发布&…
阅读更多...
Kafka 生产者优化与数据处理经验

Kafka 生产者优化与数据处理经验

Kafka&#xff1a;分布式消息系统的核心原理与安装部署-CSDN博客 自定义 Kafka 脚本 kf-use.sh 的解析与功能与应用示例-CSDN博客 Kafka 生产者全面解析&#xff1a;从基础原理到高级实践-CSDN博客 Kafka 生产者优化与数据处理经验-CSDN博客 Kafka 工作流程解析&#xff1a…
阅读更多...
【强化学习的数学原理】第02课-贝尔曼公式-笔记

【强化学习的数学原理】第02课-贝尔曼公式-笔记

学习资料&#xff1a;bilibili 西湖大学赵世钰老师的【强化学习的数学原理】课程。链接&#xff1a;强化学习的数学原理 西湖大学 赵世钰 文章目录 一、为什么return重要&#xff1f;如何计算return&#xff1f;二、state value的定义三、Bellman公式的详细推导四、公式向量形式…
阅读更多...
006-自定义枚举注解

006-自定义枚举注解

自定义枚举注解 一、业务需求描述1.问题描述2.解决方案 二、创建一个描述注解三、创建一个枚举注解四、创建一个枚举五、创建一个配置文件六、场景实战1.在 RequestParam 前面使用2.在非 Model 的实体类上使用3.在 RequestBody 对应的实体类中使用 七、效果展示 一、业务需求描…
阅读更多...
数据库表设计范式

数据库表设计范式

华子目录 MYSQL库表设计&#xff1a;范式第一范式&#xff08;1NF&#xff09;第二范式&#xff08;2NF&#xff09;第三范式&#xff08;3NF&#xff09;三范式小结巴斯-科德范式&#xff08;BCNF&#xff09;第四范式&#xff08;4NF&#xff09;第五范式&#xff08;5NF&…
阅读更多...
力扣刷题--21.合并两个有序链表

力扣刷题--21.合并两个有序链表

I am the best &#xff01;&#xff01;&#xff01; 题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1&#xff1a; 输入&#xff1a;l1 [1,2,4], l2 [1,3,4] 输出&#xff1a;[1,1,2,3,4,4] 示例 2…
阅读更多...
【java-Neo4j 5开发入门篇】-最新Java开发Neo4j

【java-Neo4j 5开发入门篇】-最新Java开发Neo4j

系列文章目录 前言 上一篇文章讲解了Neo4j的基本使用&#xff0c;本篇文章对Java操作Neo4j进行入门级别的阐述&#xff0c;方便读者快速上手对Neo4j的开发。 一、开发环境与代码 1.docker 部署Neo4j #这里使用docker部署Neo4j,需要镜像加速的需要自行配置 docker run --name…
阅读更多...
三层交换机静态路由实验

三层交换机静态路由实验

1、前置知识 2、实验目的 3、实验器材&#xff1a; 3560-23PS交换机2台、主机4台、交叉线1根和直通网线4根。 4、实验规划及拓扑 实验要求&#xff1a; &#xff08;1&#xff09;在交换机A和交换机B上分别划分基于端口的VLAN&#xff1a; 交换机 VLAN 端口成员 交换机…
阅读更多...
基于Java Springboot付费自习室管理系统

基于Java Springboot付费自习室管理系统

一、作品包含 源码数据库设计文档万字PPT全套环境和工具资源部署教程 二、项目技术 前端技术&#xff1a;Html、Css、Js、Vue、Element-ui 数据库&#xff1a;MySQL 后端技术&#xff1a;Java、Spring Boot、MyBatis 三、运行环境 开发工具&#xff1a;IDEA/eclipse 数据…
阅读更多...
深度学习笔记24_天气预测

深度学习笔记24_天气预测

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 | 接辅导、项目定制 一、我的环境 1.语言环境&#xff1a;Python 3.9 2.编译器&#xff1a;Pycharm 3.深度学习环境&#xff1a;TensorFlow 2.10.0 二、GPU设置…
阅读更多...
node报错：Error: Cannot find module ‘express‘

node报错：Error: Cannot find module ‘express‘

报错信息&#xff1a; Error: Cannot find module express 分析原因&#xff1a; 项目中需要express工具&#xff0c;但是import引入不进来&#xff0c;说明在这个项目中我们本没有对express工具包进行install&#xff0c;从我们项目中的package.json也可以看到&#xff08;并…
阅读更多...
【课堂笔记】隐私计算实训营第四期：“隐语”可信隐私计算开源框架

【课堂笔记】隐私计算实训营第四期：“隐语”可信隐私计算开源框架

“隐语”可信隐私计算开源框架 隐语架构一览隐语架构拆解产品层算法层PSI/PIR数据分析&#xff08;Data Analysis&#xff09;联邦学习&#xff08;Federated Learning&#xff09; 计算层混合编译调度——RayFedSPUHEUTEEUYACL 资源层KUSCIA 互联互通跨域管控 隐语架构一览 隐…
阅读更多...
Halo 正式开源: 使用可穿戴设备进行开源健康追踪

Halo 正式开源: 使用可穿戴设备进行开源健康追踪

在飞速发展的可穿戴技术领域&#xff0c;我们正处于一个十字路口——市场上充斥着各式时尚、功能丰富的设备&#xff0c;声称能够彻底改变我们对健康和健身的方式。 然而&#xff0c;在这些光鲜的外观和营销宣传背后&#xff0c;隐藏着一个令人担忧的现实&#xff1a;大多数这些…
阅读更多...
Java项目实战II基于微信小程序的电影院买票选座系统（开发文档+数据库+源码）

Java项目实战II基于微信小程序的电影院买票选座系统（开发文档+数据库+源码）

目录 一、前言 二、技术介绍 三、系统实现 四、核心代码 五、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末 一、前言 在数字化时代&#xff0c;…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023