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

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...