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

树状数组的推导

两个基础操作

模板-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年人工智能专业可以考哪些证书呢?
人工智能是目前全球热门的专业领域之一,随着人工智能应用范围的不断扩大,越来越多的人开始关注人工智能相关证书的获取。那么,人工智能专业可以考什么证书呢?本文将为大家介绍人工智能相关证书的种类。 人工智能机器视觉应用工程师…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
