当前位置: 首页 > 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; 该段文字…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁

赛门铁克威胁猎手团队最新报告披露&#xff0c;数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据&#xff0c;严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能&#xff0c;但SEMR…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究

摘要&#xff1a;在消费市场竞争日益激烈的当下&#xff0c;传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序&#xff0c;探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式&#xff0c;分析沉浸式体验的优势与价值…...

HTTPS证书一年多少钱?

HTTPS证书作为保障网站数据传输安全的重要工具&#xff0c;成为众多网站运营者的必备选择。然而&#xff0c;面对市场上种类繁多的HTTPS证书&#xff0c;其一年费用究竟是多少&#xff0c;又受哪些因素影响呢&#xff1f; 首先&#xff0c;HTTPS证书通常在PinTrust这样的专业平…...

js 设置3秒后执行

如何在JavaScript中延迟3秒执行操作 在JavaScript中&#xff0c;要设置一个操作在指定延迟后&#xff08;例如3秒&#xff09;执行&#xff0c;可以使用 setTimeout 函数。setTimeout 是JavaScript的核心计时器方法&#xff0c;它接受两个参数&#xff1a; 要执行的函数&…...