[蓝桥杯学习] 树状树组

lowbit操作

数字二进制表达中的最低位1以及后面所有的0,函数写法如下:

int lowbit(int x){return x&-x;}

例如说,lowbit(0101100100) = (100)

lowbit(4) = 4  lowbit(6) = 2  

时间复杂度o(1)

树状数组

应用

进行单点修改和区间查询,时间复杂度为O(logn)

结构

进行单点修改

修改t[i],然后 i=i+lowbit(i) ,修改t[i] 

进行区间查询

查询区间和,就拆分成求前缀和,求(a,b),就拆成(1,b)-(1,a-1)

i=i-lowbit(i)

修改和查询函数的代码

注意,一定是 >0

例题

愉悦值的计算就是求区间和

有两个操作,修改和查询,使用树状数组的数据结构。

#include <iostream>
using namespace std;const int N = 1e7;
using ll = long long;
ll a[N],t[N];
int n;int lowbit(int x) {return x&-x;}void update(int k,ll x)
{a[k] += x;for(int i = k ; i <= n ;i += lowbit(i)) t[i] += x;
}ll getprefix(int k)
{ll res = 0;for(int i = k ; i > 0 ; i -= lowbit(i)) res += t[i];return res;
}ll getsum(int l,int r)
{return getprefix(r) - getprefix(l-1);
}ll oper(int k,int n)
{return (2*k-n-1)*a[k]-getsum(1,k-1)+getsum(k+1,n);
}int main()
{// 请在此输入您的代码int m;cin >> n >> m;for(int i = 1 ; i <= n ; i++) {ll x;cin >> x;update(i,x);}while(m--){int op;cin >> op;if(op == 1){int x;ll z;cin >> x;cin >> z;update(x,z-a[x]);}else {int x;cin >> x;cout << oper(x,n) << '\n';}}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/232137.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

本地计算机 上的 My5OL808 服务启动后停止,某些服务在未由其他服务或程序使用时将自动停止

客户反馈说mysql启动不了&#xff0c;报错信息&#xff1a; 本地计算机 上的 My5OL808 服务启动后停止&#xff0c;某些服务在未由其他服务或程序使用时将自动停止。 查了不少资料&#xff0c;最后分析问题是这样的&#xff0c;手动或者重复安装mysql时&#xff0c;创建了多个…

tp8/6 插件PhpOffice\PhpSpreadsheet导入表格

一、安装 composer require phpoffice/phpspreadsheet 官网&#xff1a;phpoffice/phpspreadsheet - Packagist 二、代码 <?php namespace app\services\upload\model; use app\services\BaseServices; use \PhpOffice\PhpSpreadsheet\Spreadsheet; use \PhpOffice\Php…

iOS苹果和Android安卓测试APP应用程序的区别差异

在移动应用开发中&#xff0c;测试是一个至关重要的环节。无论是iOS苹果还是Android安卓&#xff0c;测试APP应用程序都需要注意一些差异和细节。本文将详细介绍iOS和Android的测试差异&#xff0c;包括操作系统版本、设备适配、测试工具和测试策略&#xff0c;并回答一些新手容…

面部识别技术的突破:IP-Adapter-FaceID实现上传照片秒变多面人生

IP-Adapter-FaceID通过上传个人照片&#xff0c;仅需几分钟即可克隆一个高度真实的个性化面部图像。IP-Adapter-FaceID的独特之处在于&#xff0c;它不仅捕捉到个体的基本外貌特征&#xff0c;更深入地嵌入了面部识别模型的面部ID&#xff0c;使生成的图像在细节上更为准确和逼…

认识SpringBoot项目中的Starter

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; 循序渐进学SpringBoot ✨特色专栏&…

[C#]yolov8-onnx在winform部署手势识别模型

【官方框架地址】 https://github.com/ultralytics/ultralytics.git 【算法介绍】 YOLOv8 是一个 SOTA 模型&#xff0c;它建立在以前 YOLO 版本的成功基础上&#xff0c;并引入了新的功能和改进&#xff0c;以进一步提升性能和灵活性。具体创新包括一个新的骨干网络、一个新…

OpenCV图像处理——C++实现亚像素尺寸标定板边缘轮廓提取

前言 标定模板&#xff08;Calibration Target&#xff09;在机器视觉、图像测量、摄影测量以及三维重建等应用中起着重要的作用。它被用于校正相机的畸变&#xff0c;确定物理尺寸和像素之间的换算关系&#xff0c;并建立相机成像的几何模型。通过使用相机拍摄带有固定间距图…

商智C店H5性能优化实战

前言 商智C店&#xff0c;是依托移动低码能力搭建的一个应用&#xff0c;产品面向B端商家。随着应用体量持续增大&#xff0c;考虑产品定位及用户体验&#xff0c;我们针对性能较差页面做了一次优化&#xff0c;并取得了不错的效果&#xff0c;用户体验值&#xff08;UEI&…

五步解决Ubuntu界面太小的问题

名人说&#xff1a;莫听穿林打叶声&#xff0c;何妨吟啸且徐行。—— 苏轼《定风波莫听穿林打叶声》 Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#xff09; 对于20版本及以上的unbuntu我们可以通过安装open-vm-tools来解决界面大小的问题&#xff0c;具体步骤如…

深度学习中的自动化标签转换:对数据集所有标签做映射转换

在机器学习中&#xff0c;特别是在涉及图像识别或分类的项目中&#xff0c;标签数据的组织和准确性至关重要。本文探讨了一个旨在高效转换标签数据的 Python 脚本。该脚本在需要更新或更改类标签的场景中特别有用&#xff0c;这是正在进行的机器学习项目中的常见任务。我们将逐…

差分电路原理以及为什么输出电压要偏移

我们在使用放大器芯片的时候&#xff0c;除了对放大器芯片本身应用外&#xff0c;通常还需要搭建一些外围电路来满足放大器芯片的使用条件&#xff0c;最终满足应用的功能&#xff0c;下面通过一个差分电路来熟悉这些应用。 差分运算放大电路&#xff0c;对共模信号得到有效抑…

Mac打包Unix可执行文件为pkg

Mac打包Unix可执行文件为pkg 方式一&#xff1a;通过packages页面打包 1.下载packages app Distribution&#xff1a;自定义化更高&#xff0c;包括修改安装页面的内容提示 我这里主要演示Distribution模式的项目&#xff1a;通过unix可执行文件postinstall.sh脚本实现通过ma…

关于java栈和堆

关于java栈和堆 在上一篇文章中我们了解了数组的声明和创建&#xff0c;本篇文章中我们了解一下声明数组&#xff0c;创建数组&#xff0c;给数组赋值以后&#xff0c;栈和堆都是怎么样子分配的&#xff0c;了解一下底层的逻辑知识&#xff0c;让大家可以更好的理解数组&#…

【Unity 实用工具篇】| 游戏多语言解决方案,官方插件Localization 实现本地化及多种语言切换

前言 【Unity 实用工具篇】| 游戏多语言解决方案&#xff0c;官方插件Localization 实现本地化及多种语言切换一、多语言本地化插件 Localization1.1 介绍1.2 效果展示1.3 使用说明 二、 插件导入并配置2.1 安装 Localization2.2 全局配置 三、多语言映射表3.1 创建多语言文本配…

el-form点击提交后把验证失败的数据传给了后端

问题&#xff1a;版本号需要根据后端返回的结果查看是否可用&#xff0c;在这里1.0.0是不可用的&#xff0c;如果点击其他地方则会报红&#xff0c;可是直接点击提交&#xff0c;则会把1.0.0这个错误的数据也提交给后端。 解决方案&#xff1a; html代码&#xff1a; <el…

C++上位软件通过LibModbus开源库和西门子S7-1200/S7-1500/S7-200 PLC进行ModbusTcp 和ModbusRTU 通信

前言 一直以来上位软件比如C等和西门子等其他品牌PLC之间的数据交换都是大家比较头疼的问题&#xff0c;尤其是C上位软件程序员。传统的方法一般有OPC、Socket 等&#xff0c;直到LibModbus 开源库出现后这种途径对程序袁来说又有了新的选择。 Modbus简介 Modbus特点 1 &#…

C# Attribute特性实战(1):Swtich判断优化

文章目录 前言简单Switch问题无参Swtich方法声明Swtich Attribute声明带有Swtich特性方法主方法结果 有参Switch修改代码修改运行过程运行结果 总结 前言 在经过前面两章内容的讲解&#xff0c;我们已经简单了解了如何使用特性和反射。我们这里解决一个简单的案例 C#高级语法 …

KVM虚拟化技术

在当今的云计算时代&#xff0c;虚拟化技术已经成为了企业和个人用户的首选。而在众多虚拟化技术中&#xff0c;KVM&#xff08;Kernel-based Virtual Machine&#xff09;虚拟化技术因其高性能、低成本和灵活性而备受青睐。本文将介绍KVM虚拟化技术的原理、特点以及应用场景。…

ClickHouse基础介绍

目录 前言 1、什么是clickhouse 2、OLAP场景的关键特征 3、列式存储更适合于OLAP场景的原因 4、clickhouse的独特功能 5、clickhouse的缺点 6、性能 6.1、单个大查询的吞吐量 6.2、处理短查询的延迟时间 6.3、处理大量短查询的吞吐量 6.4、数据的写入性能 前言 11月…

【Proteus仿真】【Arduino单片机】水箱液位监控系统

文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用Proteus8仿真Arduino单片机控制器&#xff0c;使用LCD1602液晶、按键、蜂鸣器、液位传感器、ADC转换器、水泵等。 主要功能&#xff1a; 系统运行后&#xff0c;LCD1602显示当前水位、上下限阈…