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

树状数组基础知识

lowbit:

lowbit(x)=x&(-x)

树状数组:

树状数组的功能:

数组a_{1} a_{2} a_{3} a_{4} a_{5}...a_{n}

在O(1)的时间复杂度实现单点加:a_{i}+d

在O(lng n)的时间复杂度实现查询前缀和:\sum_{1}^{x}ai

树状数组的定义:
c_{i}=\sum_{i-lowbit(i)+1}^{i} a_{i}

查询前x项的和操作:

ll query(int x){ll s=0;for( ; x; x-=x&(-x)){s+=c[x];}return s;
}

单点加操作:

//原数组长度为n
void modify(int x,ll s){for(;x<=n;x+=x&(-x)){c[x]+=s;}//如果需要别忘了把元素组对应的一位也进行变换
}

构造一个树状数组:

//原数组长度为n
scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",a+i);modify(i,a[i]);}

在输入元素的每一位时对应的在树状数组的位置加上该值。

相关文章:

树状数组基础知识

lowbit: lowbit(x)x&(-x) 树状数组&#xff1a; 树状数组的功能&#xff1a; 数组 在O(1)的时间复杂度实现单点加&#xff1a; 在O(lng n)的时间复杂度实现查询前缀和&#xff1a; 树状数组的定义&#xff1a; 查询前x项的和操作&#xff1a; ll query(int x){ll s0;f…...

【3分钟准备前端面试】vue3

目录 Vue3比vue2有什么优势vue3升级了哪些重要功能生命周期变化Options APIComposition APIreftoRef和toRefstoReftoRefsHooks (代码复用)Vue3 script setupsetupdefineProps和defineEmitsdefineExposeVue3比vue2有什么优势 性能更好体积更小更好的TS支持更好的代码组织更好的逻…...

【数据采集】亮数据浏览器、亮网络解锁器实战指南

前言 继上次我们写了数据采集与AI分析&#xff0c;亮数据通义千问助力跨境电商前行的文章之后&#xff0c;好多小伙伴来后台留言&#xff0c;表示对亮数据的数据采集非常感兴趣&#xff0c;并且感觉用起来非常顺手&#xff0c;大大减少了小白用户获取数据的成本。 在这儿&…...

暑期编程预习指南

暑期编程预习指南 高考结束后&#xff0c;迎来的是一段难得的假期时光。对于那些有志于踏入IT领域的高考生来说&#xff0c;这段时间无疑是一个重要的起点。为了帮助你们更好地利用这个假期&#xff0c;为未来的学习和职业生涯打下坚实的基础&#xff0c;特此提供一份编程预习…...

将带有 商店idr 商品信息的json导入到mongodb后,能不能根据商店id把所有商品全部提取并转为电子表格

当您已经将包含商店ID&#xff08;如realMallId&#xff09;的商品信息导入MongoDB后&#xff0c;确实可以轻松地根据商店ID提取所有相关商品信息并转换为电子表格&#xff08;例如Excel&#xff09;。这里是一个简化的流程&#xff0c;使用Python的pymongo库来查询MongoDB&…...

深入解析 androidx.databinding.BaseObservable

在现代 Android 开发中&#xff0c;数据绑定 (Data Binding) 是一个重要的技术&#xff0c;它简化了 UI 和数据之间的交互。在数据绑定框架中&#xff0c;androidx.databinding.BaseObservable 是一个关键类&#xff0c;用于实现可观察的数据模型。本文将详细介绍 BaseObservab…...

MySQL数据恢复(适用于误删后马上发现)

首先解释一下标题&#xff0c;之所以适用于误删后马上发现是因为太久了之后时间和当时操作的数据表可能会记不清楚&#xff0c;不是因为日志丢失 1.首先确保自己的数据库开启了binlog&#xff08;我的是默认开启的我没有配置过&#xff09; 根据这篇博客查看自己的配置和自己…...

[数据结构】——七种常见排序

文章目录 前言 一.冒泡排序二.选择排序三.插入排序四.希尔排序五.堆排序六.快速排序hoare挖坑法前后指针快排递归实现&#xff1a;快排非递归实现&#xff1a; 七、归并排序归并递归实现&#xff1a;归并非递归实现&#xff1a; 八、各个排序的对比图 前言 排序&#xff1a;所谓…...

CPU占用率飙升至100%:是攻击还是正常现象?

在运维和开发的日常工作中&#xff0c;CPU占用率突然飙升至100%往往是一个令人紧张的信号。这可能意味着服务器正在遭受攻击&#xff0c;但也可能是由于某些正常的、但资源密集型的任务或进程造成的。本文将探讨如何识别和应对服务器的异常CPU占用情况&#xff0c;并通过Python…...

java如何替换字符串中给定索引的字符

java如果要修改给定字符串的索引字符&#xff0c;需要用到setCharAt方法 它的语法格式是 sbf.setCharAt(index,ch) 其中&#xff1a; sbf是任意StringBuffer对象 index是被替换字符的索引 ch是替换后的索引 如果是修改一个字符就用这个方法。如果是批量修改&#xff0c;…...

基于RK3588的GMSL、FPDLink 、VByone及MIPI等多种摄像模组,适用于车载、机器人工业图像识别领域

机器人&工业摄像头 针对机器人视觉与工业检测视觉&#xff0c;信迈自主研发和生产GMSL、FPDLink 、VByone及MIPI等多种摄像模组&#xff0c;并为不同应用场景提供多种视场角度和镜头。拥有资深的图像算法和图像ISP专家团队&#xff0c;能够在软件驱动层开发、ISP算法、FPG…...

Windows 的 MFC开发的使用示例——讲得挺好的

【Visual Studio 2019】创建 MFC 桌面程序 ( 安装 MFC 开发组件 | 创建 MFC 应用 | MFC 应用窗口编辑 | 为按钮添加点击事件 | 修改按钮文字 | 打开应用 )-腾讯云开发者社区-腾讯云 (tencent.com)...

Spring4.3.x xml配置文件搜索和解析过程

###概述 这篇文章的研究不只是涉及到spring如何创建一个BeanDefinition对象&#xff0c;还涉及到spring如何加载文件、如何读取XML文件、以及我们在使用spring的时候如何扩展spring的配置。 spring在创建BeanFactory时会把xml配置文件和注解信息转换为一个个BeanDefinition对…...

网络爬虫(一)深度优先爬虫与广度优先爬虫

1. 深度优先爬虫&#xff1a;深度优先爬虫是一种以深度为优先的爬虫算法。它从一个起始点开始&#xff0c;先访问一个链接&#xff0c;然后再访问该链接下的链接&#xff0c;一直深入地访问直到无法再继续深入为止。然后回溯到上一个链接&#xff0c;再继续深入访问下一个未被访…...

JavaScript懒加载图像

懒加载图像是一种优化网页性能的技术&#xff0c;它将页面中的图像延迟加载&#xff0c;即在用户需要查看它们之前不会立即加载。这种技术通常用于处理大量或大尺寸图像的网页&#xff0c;特别是那些包含长页面或大量媒体内容的网站。 好处 **1. 加快页面加载速度&#xff1a…...

Git指令

一 参考&#xff1a;https://zhuanlan.zhihu.com/p/389814854 1.clone远程仓库 git clone https://git.xiaojukeji.com/falcon-mg/dagger.git 2.增加当前子目录下所有更改过的文件至index git add . 3.提交并备注‘xxx’ git commit -m ‘xxx’ 4.显示本地分支 git branch 5.显…...

DllImport进阶:参数配置与高级主题探究

深入讨论DllImport属性的作用和配置方法 在基础篇中&#xff0c;我们已经简单介绍了DllImport的一些属性。现在我们将深入探讨这些属性的实际应用。 1. EntryPoint EntryPoint属性用于指定要调用的非托管函数的名称。如果托管代码中的函数名与非托管代码中的函数名不同&#…...

HTTP与HTTPS协议区别及应用场景

HTTP&#xff08;超文本传输​​协议&#xff09;和 HTTPS&#xff08;安全超文本传输​​协议&#xff09;都是用于通过网络传输数据的协议。虽然它们有一些相似之处&#xff0c;但在安全性和数据保护方面也存在显著差异。 在这篇博文中&#xff0c;我们将探讨 HTTP 和 HTTPS…...

Vue2-Vue Router前端路由实现思路

1.路由是什么&#xff1f; Router路由器&#xff1a;数据包转发设备&#xff0c;路由器通过转发数据包&#xff08;数据分组&#xff09;来实现网络互连 Route路由&#xff1a;数据分组从源到目的地时&#xff0c;决定端到端路径的网络范围的进程 | - 网络层 Distribute分发…...

2024 年 亚太赛 APMCM (C题)中文赛道国际大学生数学建模挑战赛 | 量子计算的物流配送 | 数学建模完整代码+建模过程全解全析

当大家面临着复杂的数学建模问题时&#xff0c;你是否曾经感到茫然无措&#xff1f;作为2022年美国大学生数学建模比赛的O奖得主&#xff0c;我为大家提供了一套优秀的解题思路&#xff0c;让你轻松应对各种难题&#xff01; 完整内容可以在文章末尾领取&#xff01; 该段文字…...

Python合并Excel文档

有若干个Excel文档&#xff0c;每个文档格式一致&#xff0c;及第一行为文件标题&#xff0c;第二行为表格表头&#xff08;表头不完全一致&#xff09;。现需要将他们合并。合并规则为&#xff1a;去掉每个文档的第一行&#xff0c;以第二行为表头&#xff0c;将每个文档的第三…...

基于Arduino的智能蓝调节拍器:DIY音乐练习伴侣

1. 项目概述&#xff1a;一个能“演奏”蓝调的低成本节拍器玩乐器的人&#xff0c;对节拍器这东西又爱又恨。它像一位严厉的监工&#xff0c;用单调的“嘀嗒”声强迫你跟上节奏。但你想过没有&#xff0c;这个监工其实可以很有趣&#xff1f;几年前&#xff0c;我在练习蓝调吉他…...

rk35xx 通过recovery升级问题

Firefly 的 recovery 库是一个核心组件&#xff0c;它构建了一个独立的微型 Linux 系统&#xff0c;专门用于在设备主系统之外执行高可靠性的固件升级。简单来说&#xff0c;它的工作流程是&#xff1a;主系统通过命令触发&#xff0c;将升级指令写入特定分区并重启&#xff1b…...

转行网络安全运维:从0到1的可落地指南

转行网络安全运维&#xff1a;从0到1的可落地指南 一、 「3个核心技能&#xff1a;从零起步也能会」 网上学习资料多到爆炸&#xff0c;不用纠结“哪个最好”&#xff0c;记住一句话&#xff1a;**能学会、能上手的就是好的**&#xff01;不管是免费视频还是付费课&#xff0c…...

3分钟快速安装BetterNCM插件管理器,让你的网易云音乐功能翻倍

3分钟快速安装BetterNCM插件管理器&#xff0c;让你的网易云音乐功能翻倍 【免费下载链接】BetterNCM-Installer 一键安装 Better 系软件 项目地址: https://gitcode.com/gh_mirrors/be/BetterNCM-Installer 还在为网易云音乐功能单一而烦恼吗&#xff1f;想要解锁更多个…...

LoRa物联网与动态基线算法在养殖体温监测中的实战应用

1. 项目概述&#xff1a;为什么我们需要一个智能体温监测系统&#xff1f;在规模化养殖场里干了十几年&#xff0c;我见过太多因为体温异常没被及时发现而导致的损失。一头育肥猪突然不吃食&#xff0c;等饲养员第二天巡栏发现时&#xff0c;可能已经高烧好几天&#xff0c;继发…...

JMeter实现RSA签名验签全流程实战

1. 为什么RSA加密接口测试总卡在“连通但失败”这一步&#xff1f; 你有没有遇到过这种情况&#xff1a;接口文档写得清清楚楚&#xff0c;Postman里填好URL、Header、Body&#xff0c;一发请求——返回 {"code":4001,"msg":"签名验证失败"} …...

【小白快速上手】 OpenClaw 安装部署全流程(含安装包)

OpenClaw 一键安装包&#xff5c;一键部署&#xff0c;告别复杂环境配置 适配系统&#xff1a;Windows10/11 64 位当前版本&#xff1a;v2.7.5&#xff08;虾壳云版&#xff09;核心优势&#xff1a;全程可视化操作&#xff0c;无需命令行、无需手动配置 Python/Node.js&#…...

Python爬虫避坑手册:10年爬取经验总结,看完再也不会被封IP

做爬虫这么多年,我见过太多新手从入门到放弃,不是因为学不会Python,而是被各种反爬机制虐得怀疑人生。 我刚入行的时候,写的第一个爬虫是爬某电商网站的商品价格。当时觉得爬虫不就是发个请求,解析个HTML吗?结果代码刚跑了5分钟,IP就被封了。我当时还傻乎乎地重启路由器…...

Go语言调试技巧:Delve调试器

Go语言调试技巧&#xff1a;Delve调试器 1. Delve使用 dlv debug main.go (dlv) breakpoint main.go:10 (dlv) continue2. 总结 Delve是Go语言的官方调试器&#xff0c;支持断点、单步执行等调试功能。...