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

高级数据结构-树状数组

介绍

树状数组的推导

两个基础操作

模板-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 &#xff0c;返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数&#xff0c;其值等于另一个整数的平方&#xff1b;换句话说&#xff0c;其值等于一个整数自乘的积。例如&#xff0c;1、4、9 和 16 都是完全平方数&#xff0c;而 3 和 11 不是。 …...

Scala 隐式转换

object test {//复习隐式转换&#xff1a;//隐式转换&#xff1a;编译器 偷偷地&#xff0c;自动地帮我们把一种数据转换为另一种类型//例如&#xff1a;int --> double//它有失败的时候&#xff08;double --> int&#xff09;&#xff0c;有成功的时候//当它转换失败的…...

K8S命令部署后端(流水线全自动化部署)

前言 本文为链接: 云效流水线k8s半自动部署java&#xff08;保姆级&#xff09;的补充,本文起初的目的是为了补充完善k8s流水线的全自动化部署,但是也适用于k8s的一键重启,因为使用k8s的web页面容易出现漏点的情况,因此也可以把代码保存为shell脚本,同样可以实现一键重启。关于…...

Ubuntu中配置交叉编译工具的三条命令的详细研究

关于该把下面的三条交叉编译配置语句加到哪里&#xff0c;详情见 https://blog.csdn.net/wenhao_ir/article/details/144326545 的第2点。 现在试解释下面三条交叉编译配置语句&#xff1a; export ARCHarm export CROSS_COMPILEarm-buildroot-linux-gnueabihf- export PATH$…...

【PyQt5教程 二】Qt Designer 信号与槽的使用方法及PyQt5基本小部件说明

目录 一、信号与槽机制&#xff1a; 二、信号与槽使用方法&#xff1a; &#xff08;1&#xff09;使用Qt Designer 的信号与槽编辑器&#xff1a; &#xff08;2&#xff09;使用固定语法直接建立信号槽连接&#xff1a; 三、PyQt小部件及其触发信号&#xff1a; &#x…...

编程语言中接口(Interface)介绍

编程语言中接口&#xff08;Interface&#xff09;介绍 在编程语言中&#xff0c;“接口”&#xff08;Interface&#xff09;是一种抽象类型&#xff0c;定义了一组方法&#xff08;和属性&#xff09;&#xff0c;但不包含其具体实现。接口通常用于规定类必须实现的行为&…...

算法学习之贪心算法

前言 记录一下&#xff0c;免得又又忘了 贪心算法 在刚接触的时候&#xff0c;我一直觉得贪心和动态规划有相似之处&#xff0c;但做过的题目看&#xff0c;贪心似乎不用迭代...

【jvm】垃圾回收的优点和原理

目录 1. 说明2. 优点3. 原理3.1 发现无用对象3.2 回收无用对象所占用的内存 4. 回收算法4.1 标记-清除算法4.2 复制算法4.3 标记-整理算法4.4 分代收集算法 1. 说明 1.JVM&#xff08;Java虚拟机&#xff09;垃圾回收是Java语言的一大特性&#xff0c;它自动管理内存&#xff…...

YOLO系列发展历程:从YOLOv1到YOLO11,目标检测技术的革新与突破

文章目录 前言一、YOLOv1&#xff1a;单阶段目标检测的开端二、YOLOv2&#xff1a;更精准的实时检测三、YOLOv3&#xff1a;阶梯特征融合四、YOLOv4&#xff1a;性能和速度的新平衡五、YOLOv5&#xff1a;易用性和扩展性的加强六、YOLOv6&#xff1a;工业部署的利器七、YOLOv7&…...

深入浅出:序列化与反序列化的全面解析

文章目录 1. 引言2. 什么是序列化&#xff1f;2.1 为什么需要序列化&#xff1f; 3. 什么是反序列化&#xff1f;3.1 反序列化的重要性 4. 序列化与反序列化的实现4.1 JSON (JavaScript Object Notation)4.2 XML (eXtensible Markup Language)4.3 Protocol Buffers (Protobuf)4…...

word实践:正文/标题/表图等的共用模板样式设置

说在前面 最近使用word新建文件很多&#xff0c;发现要给大毛病&#xff0c;每次新建一个word文件&#xff0c;标题/正文的字体、大小和间距都要重新设置一遍&#xff0c;而且每次设置这些样式都忘记了参数&#xff0c;今天记录一下&#xff0c;以便后续方便查看使用。现在就以…...

Blender中使用BlenderGIS插件快速生成城市建筑模型

导入下载 BlenderGIS 插件 去github上下载其压缩包&#xff0c;地址如下&#xff1a; https://github.com/domlysz/BlenderGIS 在BlenderGIS中导入这个插件压缩包&#xff1a; 点击上方菜单栏的编辑&#xff0c;点击偏好设置 在插件>从磁盘安装中导入刚刚下载的压缩包 可…...

【单元测试】单元测试的重要性

1一些错误的认识 在实际的单元测试过程中总会有一些错误的认识左右着我们&#xff0c;使之成为单元测试最大的障碍&#xff0c;在此将其一一分析如下&#xff1a; 它太浪费时间了&#xff0c;现在要赶进度&#xff0c;时间上根本不允许&#xff0c;或者随便做做应付领导。 …...

Codeforces Round 992 (Div. 2)

这场cf只在b卡了一下&#xff0c;因为b真是犯蠢了&#xff0c;我以为会向下取整&#xff0c;结果是完全就不取整&#xff0c;或者说是向上取整&#xff0c;卡了我半个小时&#xff0c;要不是紧急看了题一下&#xff0c;昨天那场就毁了 话不多说&#xff0c;直接开讲 A. Game …...

el-table一键选择全部行,切换分页后无法勾选

el-table一键全选&#xff0c;分页的完美支持 问题背景尝试解决存在问题问题分析 解决方案改进思路如下具体代码实现如下 问题背景 现在有个需求&#xff0c;一个表格有若干条数据(假设数量大于20&#xff0c;每页10条&#xff0c;保证有2个以上分页即可)。 现在需要在表格上方…...

负载均衡最佳实践及自定义负载均衡器

文章目录 负载均衡最佳实践及自定义负载均衡器一、负载均衡概述二、轮询负载均衡器&#xff08;一&#xff09;理论介绍&#xff08;二&#xff09;Java 实现示例&#xff08;三&#xff09;关键步骤&#xff08;四&#xff09;流程图 三、随机负载均衡器&#xff08;一&#x…...

大模型 LMDeploy 量化部署

1 模型部署 定义&#xff1a; 在软件工程中&#xff0c;部署通常指的是将开发完毕的软件投入使用的过程。在人工智能领域&#xff0c;模型部署是实现深度学习算法落地应用的关键步骤。简单来说&#xff0c;模型部署就是将训练好的深度学习模型在特定环境中运行的过程。 场景…...

算法设计5_分支限界法

分支限界法 分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树&#xff0c;裁剪那些不能得到最优解的子树以提高搜索效率。 步骤&#xff1a; ① 定义解空间(对解编码); ② 确定解空间的树结构&#xff1b; ③ 按BFS等方式搜索&#xff1a; a.每个活…...

2025年人工智能专业可以考哪些证书呢?

人工智能是目前全球热门的专业领域之一&#xff0c;随着人工智能应用范围的不断扩大&#xff0c;越来越多的人开始关注人工智能相关证书的获取。那么&#xff0c;人工智能专业可以考什么证书呢&#xff1f;本文将为大家介绍人工智能相关证书的种类。 人工智能机器视觉应用工程师…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

SQL Server 触发器调用存储过程实现发送 HTTP 请求

文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...