树状数组-数据结构

article2025/3/11 5:28:16/文章来源:https://blog.csdn.net/qfbeqhbviq/article/details/137370662

树状数组

在这里插入图片描述

t[x] 节点的父节点为 t[x + lowbit(x)]
整棵树的深度为 log2n +1

1 . add(x,k) 给指定的节点x加上k — 动态的维护前缀和

需要从x开始，向上找到所有父节点，值都加上k
在这里插入图片描述

2. ask(x) 求取节点x之前的前缀和

求取单点之前的前缀和只需要累加即可
如果是求取指定区间的前缀和，我们只需要分别求出两个端点的前缀和然后作差即可

在这里插入图片描述
还可以进行的操作：

1、上面已经实现了单点修改，区间查询

还可以实现

2. 区间修改，单点查询

在这里插入图片描述

3. 区间修改，区间查询

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

【算法】单单单单单调栈，接接接接接雨水

【算法】单单单单单调栈，接接接接接雨水今天没有小故事。参考以及题单来源： 代码随想录 (programmercarl.com) Part 1 啥是单调栈？ 1.啥啥啥是单调栈？ 栈的特性想必各位再熟悉不过了：先进后出。栈仅仅有一个出口&a…

算法 day29 回溯5

491 非递减子序列给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情…

检测头篇 | 利用RT-DETR模型的检测头去替换YOLOv8中的检测头

前言：Hello大家好，我是小哥谈。RT-DETR号称是打败YOLO的检测模型，其作为一种基于Transformer的检测方法，相较于传统的基于卷积的检测方法，提供了更为全面和深入的特征理解，将RT-DETR检测头融入YOLOv8，我们可以结合YOLO的实时检测能力和RT-DETR的深度特征理解能力，打造出…

业务网关的设计与实践

在过去的两年里，主要在做业务网关的开发。今年春节后选择转岗去做更偏近业务的开发。公司的业务是金融相关，一直觉得金融相关的业务是有一定门槛并且是对职业生涯有帮助的，所以趁这个机会来深入了解这块业务。仔细回想，在做业务…

【数据处理包Pandas】数据载入与预处理

目录一、数据载入二、数据清洗（一）Pandas中缺失值的表示（二）与缺失值判断和处理相关的方法三、连续特征离散化四、哑变量处理准备工作导入 NumPy 库和 Pandas 库。 import numpy as np import pandas as pd一、数据载入对…

开机自启动

对win10,给一种开机自启动的设置方法: 1. winr 打开 2. 输入shell:startup打开开始\程序\启动 3. 把想要自启动的应用的快捷方式放在这里即可亲测有用

第十一届蓝桥杯物联网试题（省赛）

对于通信方面，还是终端A、B都保持接收状态，当要发送的数组不为空再发送数据，发送完后立即清除，接收数据的数组不为空则处理，处理完后立即清除，分工明确继电器不亮一般可能是电压不够将数据加空格再加\r…

RPA自动化小红书自动化写文以及发文！

1、视频演示 RPA自动化小红书自动写作发文 2、核心功能点采集笔记：采集小红书上点赞量大于1000的爆款笔记下载素材：下载爆款笔记的主图爆款改写：根据爆款笔记的标题仿写新的标题以及新的文案自动发布：将爆款笔记发布到小红…

Oracle RAC One Node，双胞胎变独生子？

📢📢📢📣📣📣 哈喽！大家好，我是【IT邦德】，江湖人称jeames007，10余年DBA及大数据工作经验一位上进心十足的【大数据领域博主】！😜&am…

LeetCode刷题实战2：两数相加

在日常我们学习数据结构和算法的知识，一定不能只停留在看书、看视频层面，一定要自己多练习，纸上得来终觉浅，绝知此事要躬行。题目内容给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存…

Vue3：组件间通信-$attrs的使用

一、情景说明我们之前学习了通过props实现，父给子传数据那么，如果，父组件给子组件传递多个数据，但是，子组件只用props声明了一个数据其他数据去哪里了呢？ 二、案例 1、父组件 <Child :a"a&…

Linux 关闭防火墙命令（新手）

关闭防火墙查看防火墙状态 systemctl status firewalld.service 临时关闭防火墙（重启失效） systemctl stop firewalld.service 永久关闭防火墙 systemctl disable firewalld.servicesudo systemctl enable firewalld，这种方式输入命令…

AcWing 731. 毕业旅行问题（每日一题）

原题链接：731. 毕业旅行问题 - AcWing题库此题难度较大，是2019年字节跳动校招题，里面涉及位运算与状态压缩DP，不会的可以去学习，此题根据个人量力而行。建议看一下y总的讲解：AcWing 731. 毕业旅行问题&…

【Unity 实用工具篇】| Unity中实现背景模糊效果，简单易用

前言【Unity 实用工具篇】| Unity 实现背景模糊效果，简单易用一、实现背景模糊效果1.1 介绍1.2 效果展示1.3 使用说明及下载二、插件资源简单介绍2.1 导入下载好的资源2.2 功能介绍2.2.1 捕获特效2.2.2 高级选项

长连接详解

一分钟了解长连接、短连接、心跳机制与断线重连 - 知乎 (zhihu.com) websocket 实现长连接原理_websocket 是长连接吗-CSDN博客

RedisDesktopManager 安装

简介：安装redis可视化工具一、下载压缩包 Redis 可视化工具链接：https://pan.baidu.com/s/1P2oZx9UpQbXDsxJ3GPUeOQ 提取码：6rft Redis 命令窗口版本链接：https://pan.baidu.com/s/1mIuxCEWwD__aoqp1Cx8MFQ 提取码&#xf…