高级数据结构-树状数组
介绍

树状数组的推导

两个基础操作

模板-acwing795. 前缀和
#include<bits/stdc++.h>
using namespace std;const int N = 1e6+10;
int c[N]; int lowbit(int x){return x & -x;
}int query(int x){int ans = 0;for(; x; x -= lowbit(x)) ans += c[x];return ans;
}void add(int x,int y){for(; x <= N; x += lowbit(x)) c[x] += y;
}int main(){int n,m; scanf("%d%d",&n,&m);for(int i = 1; i <= n; i++){int num; scanf("%d",&num);add(i,num);}while(m--){int l,r; scanf("%d%d",&l,&r);printf("%d\n",query(r)-query(l-1));}return 0;
}
模板-acwing5910. 求逆序对
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int N = 1e6+10;
LL c[N],a[N];int lowbit(int x) // 返回末尾的1
{return x & -x;
}LL query(int x){LL ans = 0;for(; x; x -= lowbit(x)) ans += c[x];return ans;
}void add(int x,int y){for(; x <= N; x += lowbit(x)) c[x] += y;
}int main()
{LL ans = 0;int n; scanf("%d",&n);for(int i = 1; i <= n; i++){scanf("%d",&a[i]);}//倒序扫描,找值比当前这个数小但是先进入树状数组的数,即1-(a[i]-1)的和for(int i = n; i >= 1; i--){ans += query(a[i]-1)-query(0);add(a[i],1);}printf("%lld\n",ans);return 0;
}
相关文章:
高级数据结构-树状数组
介绍 树状数组的推导 两个基础操作 模板-acwing795. 前缀和 #include<bits/stdc.h> using namespace std;const int N 1e610; int c[N]; int lowbit(int x){return x & -x; }int query(int x){int ans 0;for(; x; x - lowbit(x)) ans c[x];return ans; }void add…...
LeetCode279. 完全平方数(2024冬季每日一题 27)
给你一个整数 n ,返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。 …...
Scala 隐式转换
object test {//复习隐式转换://隐式转换:编译器 偷偷地,自动地帮我们把一种数据转换为另一种类型//例如:int --> double//它有失败的时候(double --> int),有成功的时候//当它转换失败的…...
K8S命令部署后端(流水线全自动化部署)
前言 本文为链接: 云效流水线k8s半自动部署java(保姆级)的补充,本文起初的目的是为了补充完善k8s流水线的全自动化部署,但是也适用于k8s的一键重启,因为使用k8s的web页面容易出现漏点的情况,因此也可以把代码保存为shell脚本,同样可以实现一键重启。关于…...
Ubuntu中配置交叉编译工具的三条命令的详细研究
关于该把下面的三条交叉编译配置语句加到哪里,详情见 https://blog.csdn.net/wenhao_ir/article/details/144326545 的第2点。 现在试解释下面三条交叉编译配置语句: export ARCHarm export CROSS_COMPILEarm-buildroot-linux-gnueabihf- export PATH$…...
【PyQt5教程 二】Qt Designer 信号与槽的使用方法及PyQt5基本小部件说明
目录 一、信号与槽机制: 二、信号与槽使用方法: (1)使用Qt Designer 的信号与槽编辑器: (2)使用固定语法直接建立信号槽连接: 三、PyQt小部件及其触发信号: &#x…...
编程语言中接口(Interface)介绍
编程语言中接口(Interface)介绍 在编程语言中,“接口”(Interface)是一种抽象类型,定义了一组方法(和属性),但不包含其具体实现。接口通常用于规定类必须实现的行为&…...
算法学习之贪心算法
前言 记录一下,免得又又忘了 贪心算法 在刚接触的时候,我一直觉得贪心和动态规划有相似之处,但做过的题目看,贪心似乎不用迭代...
【jvm】垃圾回收的优点和原理
目录 1. 说明2. 优点3. 原理3.1 发现无用对象3.2 回收无用对象所占用的内存 4. 回收算法4.1 标记-清除算法4.2 复制算法4.3 标记-整理算法4.4 分代收集算法 1. 说明 1.JVM(Java虚拟机)垃圾回收是Java语言的一大特性,它自动管理内存ÿ…...
YOLO系列发展历程:从YOLOv1到YOLO11,目标检测技术的革新与突破
文章目录 前言一、YOLOv1:单阶段目标检测的开端二、YOLOv2:更精准的实时检测三、YOLOv3:阶梯特征融合四、YOLOv4:性能和速度的新平衡五、YOLOv5:易用性和扩展性的加强六、YOLOv6:工业部署的利器七、YOLOv7&…...
深入浅出:序列化与反序列化的全面解析
文章目录 1. 引言2. 什么是序列化?2.1 为什么需要序列化? 3. 什么是反序列化?3.1 反序列化的重要性 4. 序列化与反序列化的实现4.1 JSON (JavaScript Object Notation)4.2 XML (eXtensible Markup Language)4.3 Protocol Buffers (Protobuf)4…...
word实践:正文/标题/表图等的共用模板样式设置
说在前面 最近使用word新建文件很多,发现要给大毛病,每次新建一个word文件,标题/正文的字体、大小和间距都要重新设置一遍,而且每次设置这些样式都忘记了参数,今天记录一下,以便后续方便查看使用。现在就以…...
Blender中使用BlenderGIS插件快速生成城市建筑模型
导入下载 BlenderGIS 插件 去github上下载其压缩包,地址如下: https://github.com/domlysz/BlenderGIS 在BlenderGIS中导入这个插件压缩包: 点击上方菜单栏的编辑,点击偏好设置 在插件>从磁盘安装中导入刚刚下载的压缩包 可…...
【单元测试】单元测试的重要性
1一些错误的认识 在实际的单元测试过程中总会有一些错误的认识左右着我们,使之成为单元测试最大的障碍,在此将其一一分析如下: 它太浪费时间了,现在要赶进度,时间上根本不允许,或者随便做做应付领导。 …...
Codeforces Round 992 (Div. 2)
这场cf只在b卡了一下,因为b真是犯蠢了,我以为会向下取整,结果是完全就不取整,或者说是向上取整,卡了我半个小时,要不是紧急看了题一下,昨天那场就毁了 话不多说,直接开讲 A. Game …...
el-table一键选择全部行,切换分页后无法勾选
el-table一键全选,分页的完美支持 问题背景尝试解决存在问题问题分析 解决方案改进思路如下具体代码实现如下 问题背景 现在有个需求,一个表格有若干条数据(假设数量大于20,每页10条,保证有2个以上分页即可)。 现在需要在表格上方…...
负载均衡最佳实践及自定义负载均衡器
文章目录 负载均衡最佳实践及自定义负载均衡器一、负载均衡概述二、轮询负载均衡器(一)理论介绍(二)Java 实现示例(三)关键步骤(四)流程图 三、随机负载均衡器(一&#x…...
大模型 LMDeploy 量化部署
1 模型部署 定义: 在软件工程中,部署通常指的是将开发完毕的软件投入使用的过程。在人工智能领域,模型部署是实现深度学习算法落地应用的关键步骤。简单来说,模型部署就是将训练好的深度学习模型在特定环境中运行的过程。 场景…...
算法设计5_分支限界法
分支限界法 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树,裁剪那些不能得到最优解的子树以提高搜索效率。 步骤: ① 定义解空间(对解编码); ② 确定解空间的树结构; ③ 按BFS等方式搜索: a.每个活…...
2025年人工智能专业可以考哪些证书呢?
人工智能是目前全球热门的专业领域之一,随着人工智能应用范围的不断扩大,越来越多的人开始关注人工智能相关证书的获取。那么,人工智能专业可以考什么证书呢?本文将为大家介绍人工智能相关证书的种类。 人工智能机器视觉应用工程师…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...
