当前位置: 首页 > 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;本文将为大家介绍人工智能相关证书的种类。 人工智能机器视觉应用工程师…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

华硕a豆14 Air香氛版,美学与科技的馨香融合

在快节奏的现代生活中&#xff0c;我们渴望一个能激发创想、愉悦感官的工作与生活伙伴&#xff0c;它不仅是冰冷的科技工具&#xff0c;更能触动我们内心深处的细腻情感。正是在这样的期许下&#xff0c;华硕a豆14 Air香氛版翩然而至&#xff0c;它以一种前所未有的方式&#x…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

【Veristand】Veristand环境安装教程-Linux RT / Windows

首先声明&#xff0c;此教程是针对Simulink编译模型并导入Veristand中编写的&#xff0c;同时需要注意的是老用户编译可能用的是Veristand Model Framework&#xff0c;那个是历史版本&#xff0c;且NI不会再维护&#xff0c;新版本编译支持为VeriStand Model Generation Suppo…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...