树状数组初学_树状数组原地构建-程序员宅基地
技术标签： 蒟蒻sheep的刷题小集 算法 c++ 新手模板类题目 leetcode
一、树状数组的初学
之前学习过前缀和和差分的一些知识就觉得挺神奇的，然后昨天刷到力扣的每日一题之后发现，好像树状数组在多区间的修改和查询方面很神奇，包括之后要学习的线段树（能解决所有树状数组的问题）可能会更加有收获吧。
二、一些小小的理解
①lowbit的理解
在线段数组里面有这么一个重要的函数，也是能够构造整个树状数组的核心吧！代码只有一行，但是对于我这种萌新来说，刚开始还是很难理解的。代码如下：
//寻找一个数最低位的1
int lowbit(int x) {
return x & -x;
}
举个比较简单的例子，一个数为3，他的二进制表示为11，那么根据负数二进制的要求，-3的二进制，我们先求他的反码为00，最后+1得到补码为01，最后让11 & 01 便取得 01，也就是最低位的第一个1，大家可以试一下，利用这个函数，最后得到的结果一定只会含有一个1在整个数里面;
三、树状数组的构建
大家可以看到，树状数组首先对应一个s数组（假设有8个元素），也就是一个求总和的数组，这个数组里面对应装下一些前缀和，而每一个s对应数都是连续的，这也就为我们后面提供区间和利用前缀和的思想提供了很好的办法！
当然这里有要注意的点： 就是我们的s数组必须从1作为下标开始，也就是8个元素我们要开s[9]的空间，因为lowbit(0)是不存在最低位1的会造成无限循环的风险。大家可能不太理解，这个数组里面为什么能够按照这样的数字进行相加，我们看下面的图：
从上面的图，我们可以知道，每个s对应的下标，都是从某个下标i，通过加上lowbit(i),并且在每次演变的时候，让Si加上对应的num[i - 1] 的数(因为num数中的下标是从0开始的)，最后就变成了第一张图的样子，也就是接下来要讲的区间的更新。
四、区间的查询以及更新
①区间的更新：
因为有了上面的铺垫，我们直接放上，s数组更新的一个代码，也就是如何让s数组存上对应相关的值。
//添加和到对应的树状数组
void add(int x, int val) {
for(int i = x; i <= n; i += lowbit(i)) {
sum[i] += val; //这里的val其实就是num[i - 1];
}
}
经过上面的操作之后，我们就完成了s数组的构建，那么如果题目要求，改掉num数组里面的某个数的话，我们只需要让那个数所在的s也同时的更新就好，像下面一样:
void update(int index, int val) {
//这里的index要+1，因为num数组的下标从0开始
add(index + 1, val - nums[index]);
nums[index] = val;
}
②区间的查询
区间的查询，其实有点像更新的逆过程，比如我们要知道(num[0] - num[6])的总和也就是说如何要求出S7 + S6 + S4的值（这里大家可以对照一下上面的图）。7 - 6 - 4 不就是 111 - 110 - 100的过程吗？那其实就是每次让下标为i的数减去lowbit(i)，然后在此过程中去加上S[i]的值，最后就可以得到原始下标为index的前缀和了，根据区间前缀和计算的方式，最终就可以知道一段区间的和了。
//计算从下标0- x-1的前缀和
int query(int x) {
int s = 0;
for(int i = x; i > 0; i -= lowbit(i)) {
s += sum[i];
}
return s;
}
//计算区间的和(不了解前缀和的同学可以先了解一下前缀和)
int sumRange(int left, int right) {
//因为原始的下标从0开始，那么对应区间和的下标要加1
return query(right + 1) - query(left);
}
五、力扣的原题
①原题贴图
②AC的代码全贴
class NumArray {
public:
vector<int> sum;
//记录最低位的1
int lowbit(int x) {
return x & -x;
}
//添加和到对应的树状数组
void add(int x, int val) {
for(int i = x; i <= n; i += lowbit(i)) {
sum[i] += val;
}
}
int query(int x) {
int s = 0;
for(int i = x; i > 0; i -= lowbit(i)) {
s += sum[i];
}
return s;
}
vector<int> nums;
int n;
NumArray(vector<int>& nums) {
this->nums = nums;
n = nums.size();
sum.resize(n + 1, 0);
for(int i = 0; i < n; i++) {
add(i + 1, nums[i]);
}
}
void update(int index, int val) {
add(index + 1, val - nums[index]);
nums[index] = val;
}
int sumRange(int left, int right) {
return query(right + 1) - query(left);
}
};
六、 参考文档
智能推荐
vscode 更新后报错 Couldn‘t start dlv dap_couldn't start dlv dap-程序员宅基地
文章浏览阅读8.7k次，点赞2次，收藏6次。visio studio code port` is ignored with the 'dlv-dap'解决方法：在配置文件中加上， "debugAdapter":"legacy",参考博文：https://gitee.com/snow2zhou/vscode-go/blob/master/docs/dlv-dap.md_couldn't start dlv dap
[Java教程 25] 二维数组定义详解_java二维数组的定义-程序员宅基地
文章浏览阅读4.1k次，点赞5次，收藏10次。转载声明：商业转载请联系作者获得授权,非商业转载请注明出处.原文来自 呆萌钟【JavaSe必知必会】27-二维数组定义详解 二维数组概述二维数组其实就是一个元素为一维数组的数组。二维数组定义格式格式1数据类型[][] 变量名 = new 数据类型[m][n]; m表示这个二维数组有多少个一维数组 n表示每一个一维数组的元素个数 举例： int[][] arr =..._java二维数组的定义
python怎样控制继电器_Python 控制220V ？？？ 老板，你没看错！-程序员宅基地
文章浏览阅读643次。这是武散人著《自拍教程》(自动化测试Python教程)系列第60篇文章。重要提醒：本案例涉及220v危险电压上电下电测试，存在安全风险，请切勿随意尝试！！！案例故事 很多移动终端都不带电池，都是直接电源插头供电，比如Android电视机(220v)，小米小爱同学智能音箱(220v转5v的电源转换器)，智能后视镜(12v)等智能终端设备，Android家庭信息机平板(5v),还有电饭煲，微波炉，空调..._python实现继电器对android手机进行上下电
资源 | 分享几个强大的网站_电子世家-程序员宅基地
文章浏览阅读8.5k次，点赞5次，收藏9次。分享几个强大的网站：1、电子世家电子世家汇总了大量电子、嵌入式等网站、论坛。网址如下：http://www.dianzishijia.com/2、极客导航极客导航汇总了大量的技术、产品、设计、运营、职能等方面的内容。网址如下：https://www.gogeeks.cn/nav3、在线工具-程序员的工具箱这个网站有大量的在线工具可以使用，工具包含开发类、站长类、极客类、..._电子世家
css的animation动画_css animation-程序员宅基地
文章浏览阅读7.6k次，点赞2次，收藏12次。顾名思义，它可以控制动画的状态 – 运行或者暂停,类似于视频播放器的开始和暂停,是 CSS 动画中有限的控制动画状态的手段之一。在 1-2 秒范围内随机，这样，我们就可以得到非常自然且不同的上升动画效果，基本不会出现重复的画面，很好的模拟了随机效果。属性或其子属性，该属性允许配置动画时间、时长以及其他动画细节，但该属性不能配置动画的实际表现，动画的实际表现是由。中定义的第一帧这种说法，因为动画运行的第一帧和最后一帧的实际状态还会受到动画运行方向。，可以有效的构建更为随机的动画效果，让动画更加的自然。_css animation
Android 9 Audio系统笔记：AudioFlinger音频流处理流程_audio effects 的preprocess-程序员宅基地
文章浏览阅读4.9k次，点赞7次，收藏24次。好久没写了，今天碰巧有个同事问我，我就顺便写一下，后面就不用又找一遍代码了，所谓好记性不如烂笔头。这块是关于如何从AudioTrack 写入数据到audioflinger，以及audioflinger如何写入到hal层，主要写一下流程。client写入数据：//frameworks\av\media\libaudioclient\AudioTrack.cppssize_t AudioTrack::write(const void* buffer, size_t userSize, bool bloc_audio effects 的preprocess
随便推点
面试总结9-接口测试面试题：如何做接口测试_xing2516_新浪博客-程序员宅基地
文章浏览阅读415次。关于面试总结9-接口测试面试题前言接口测试最近几年被炒的火热了，越来越多的测试同行意识到接口测试的重要性。接口测试为什么会如此重要呢？主要是平常的功能点点点，大家水平都一样，是个人都能点，面试时候如果问你平常在公司怎么测试的，你除了说点点点，还能说什么呢，无非就是这个项目点完了点那个项目，这就是为什么各行各业的只要手指能点得动的人都来转行软件测试了。面试的时候面试官希..._1,没有接口文档,如何做接口测试,面试题
SAP是什么_sap scdn-程序员宅基地
文章浏览阅读8.8k次，点赞14次，收藏60次。SAP，为“System Applications and Products”的简称，是SAP公司的产品——企业管理解决方案(ERP)的软件名称。SAP公司（纽交所代码：SAP）成立于1972年。总部位于德国沃尔多夫市，在全球拥有6万多名员工，遍布全球130个国家，并拥有覆盖全球11,500家企业的合作伙伴网络。定义从企业后台到公司决策层、从工厂仓库到商铺店面、从电脑桌面到移动终端—SAP助力用户和企业高效协作，获取商业洞见，并从竞争中脱颖而出。SAP的软件和服务能够帮助客户实现盈利性的运营_sap scdn
Maven配置远程仓库-详细操作_maven-source-plugin 部署 远程仓库-程序员宅基地
文章浏览阅读4.9k次。用maven管理项目时，需要通过pom添加jar，进行maven加载，有时候在公司你需要添加公司的私服maven仓库进行拉取依赖包假设当前项目需要用到仓库(http://192.168.80.204:8081/nexus/content/groups/public/)，此时可根据maven配置的加载优先级将仓库配置到合适的位置。根据需求选择下边任意一种即可。1.pom.xml：添加如下配置到..._maven-source-plugin 部署 远程仓库
JDBC—4_jdbc4有哪些函数-程序员宅基地
文章浏览阅读353次。事务ACID原子性(atomicity)：组成事务处理的语句形成了一个逻辑单元，不能只执行其中的一部分。 一致性(consistency)：在事务处理执行前后，数据库是一致的(两个账户要么都变，或者都不变)。 隔离性(isolcation)：一个事务处理对另一个事务处_jdbc4有哪些函数
简单MFC程序开发-C++反编译肉鸡养成-程序员宅基地
文章浏览阅读4.5k次。为了更好的理解MFC（C++）程序的结构，拆解方法，需要首先创建一个MFC窗口程序，对于只了解一点C++的工程师来说，走一遍MFC程序开发的流程，是很有必有有一个指导的，无奈C++开发工具的版本太多，暴走了一段时间，终于摸索出来visual studio 2022版本的流程。_c++反编译
Bean with name ‘XX‘ has been injected into other beans [XX,XX] in its raw version.......... 错误分析及解决-程序员宅基地
文章浏览阅读2.9k次。启动出现大量异常，均以 Error create bean ‘xxx’ 开头，且很多类似如下且每一行最后末尾都会指出被循环依赖的 bean 名异常抛出由于是嵌套循环的，所以这一类错误的根本原因往往会置于每一行的最后以及日志的最后且在日志的最后一处错误会具体写出如下错误，明显说明是循环依赖错误，是在错误日志的最后一部分！会出现类似如下错误：Bean with name ‘xxxxService/dao’ has been injected into other beans [xxx,xxx,xxx] in_has been injected into other beans