关键词：
树状数组区间更新
在今天的文章开始之前，给大家提一个建议，由于线段树和树状数组这两个结构的分析有很多联系，因此，建议没有看前几篇文章的朋友一定需要了解一下前面的内容。链接如下：
上篇文章我们讨论了树状数组的基本结构以及它最擅长的两个功能：单点更新和区间求和，今天，我们来接着上一篇文章的内容继续深入研究。上篇文章我们是将树状数组和线段树进行对比讲解的，既然线段树的章节我们介绍了区间求和、区间最值、单点更新、区间更新，那么对应的，树状数组也应该有个区间更新吧。但我们从上篇文章中的分析可以看出来，树状数组确实不擅长区间更新，它也无法进行区间更新，这是不是就意味着文章写到这里就结束了呢？当然不是，作为一个求真务实从不坑蒙拐骗的诚信公众号，我当然不会做出那种用标题骗阅读量的事情。那之前说的树状数组不会、不能进行区间更新是怎么回事？答案就是树状数组可以利用某些手段（比如单点更新）来达到区间更新的目的，让结果和区间更新后的结果相吻合，看似实现了区间更新，实际是伪区间更新。所以，坑蒙拐骗的是它，可不是我。没有看过上篇文章的建议先看上篇文章（树状数组（Binary Indexed Tree,BIT））了解基础知识，便于更好的理解本篇文章。
既然它是可以实现伪区间更新的，我们做题的时候又只是追求输出结果的正确，不妨就花几分钟看一看到底它是怎么实现的？
在此我们称事先给定的数组为原数据数组，按照树状数组结构实现的数组称为树状数组，本篇文章中讨论的区间更新方式是给原数据数组一段区间的所有元素加上一个数值 a 。
从上篇文章中我们可以知道，树状数组的区间求和实际是通过区间两端点的前缀和相减实现的，检验区间更新是否正确的方式便是区间求和，既然区间求和只需要保证区间两端点的正确性，就给我们留出了可乘之机，我们可以在进行区间更新的时候只对两端点进行更新操作，保证数值正确即可。现在，我们就需要对更新后整个树状数组的特征进行观察，找出规律。
假设某次给原数据数组区间 i ～j 上的所有元素均加 a，此时若要查询某一区间 p～q 的元素和，会是怎样的结果呢？我们首先应该分别求解 p 和 q 位置的前缀和，p 和 q 求前缀和的方法是一样的，所以我们研究的问题变成了区间更新和单点查询，那么一般的我们假设求 x 的前缀和，如下图所示：
上图中， i～j 表示区间更新的范围，x 表示待求前缀和的结束元素位置， sum[x]表示区间更新前 x 位置的前缀和，a 表示区间更新过程中对每个元素增加的值，纵坐标 y 表示区间更新后相应的前缀和的增加量，即 y(x)+sum[x] 的值为区间更新后x位置的前缀和。由图可知，
在 x<i 时，y 的值恒为 0
在i <= x <= j 时，y的值随着 x 的增加而递增
在 x > j 时，y的值恒为 (j - i +1) * a
我们知道，在单点更新的时候，对一个位置 x 的值加 a 时，位置在 x 之前的所有前缀和都是没有影响的，受影响的是从 x 开始之后的所有位置的前缀和。
知道了这些之后，我们就可以利用上篇文章中实现的单点更新和区间查询进行区间更新和单点查询了，由上图可知，在 x < i 和 x > j 的范围内（待更新区间之外），只要区间更新的加数 a 确定，这些前缀和便是固定值，不需要知道单点查询时候的位置，因此这部分工作可以在更新的时候实现，具体如何实现呢？
观察上图，我们发现 在i <= x <= j 时，前缀和增量 y = (x-i+1)*a = x*a -(i-1)*a ；在 x > j 时，前缀和增量 y = (j - i +1 )*a = j*a - (i-1)*a ; 由此可以得出结论，在 x >= i 时，y 的表达式中均包含 -(i-1)*a ，所以根据前缀和的规律，我们利用单点更新将此值加在 i 位置的前缀和上，则可以达到给 x >= i 范围内的所有前缀和均加上了此值。在 i <= x <= j 的区间范围内，我们发现前缀和增量表达式 y 除 -(i-1)*a 这部分外，剩余的部分为 x*a ，x 即为单点查询的位置，这个值不确定，只有在某一次查询的时候才能被确定，因此，这个操作需要在单点查询的时候完成。在 x > j 的范围内，前缀和表达式 y ＝ j*a - (i-1)*a ， 除已经在 x = i 的位置处理的 -(i-1)*a 这部分之外，剩余部分为 j*a ，这部分值只与区间更新的端点和更新的加数 a 有关，因此可以在更新时候处理，这时候我们需要将 j＋1 位置的前缀和由 sum[ j+1 ] 更新为 sum[ j+1] + j*a 。至此，除了查询 i <= x <= j 范围的值不正确之外，其余值都能够保证正确性。
当单点查询的位置 x 在 i~j 范围内的时候，我们需要在 x 的位置 单点更新前缀和 sum[ x ] 为 sum[x] +x*a 。现在，我们已经将三个区间都处理结束了，对吗？但是，这是真的结束吗？ 大家是否还记得单点更新的操作？操作是这样的：在单点更新的时候，对一个位置 x 的值加 a 时，位置在 x 之前的所有前缀和都是没有影响的，受影响的是从 x 开始之后的所有位置的前缀和。这也就意味着当单点查询的位置 x 在 i~j 范围内的时候，我们对 x 位置的单点更新实际上已经影响到了我们在区间更新时候已经处理好的区间 x > j ，因此我们需要将此处因单点更新加的值 x＊a 减去。这也就意味着，我们需要将加数 a 存储起来，否则，等到单点查询的时候，加数 a 都已经变成若干次区间查询后的加数了。但由于，同一个区间的加数多次叠加后，结果还是正确的。因此，我们可以仿照线段树时的 lazy_tag 想法存储每个节点对应的加数（线段树 lazy_tag相关知识详见：线段树第二弹（区间更新））。
对于某一个具体的加数该如何存储和维护呢？有了前面的分析思路，我们应该可以用两个树状数组分别存储前缀和与加数，其中一个树状数组 lazy_tag来存储加数，假设某次区间更新的范围为 i～j ，加数为 a ，我们需要做的操作为：
lazy_tag[i] += a ; //给 x >= i 的所有节点加数均加 a
lazy_tag[j+1] -= a ; // 给 x >j 的所有节点均减 a ，消除 i 位置处理的影响
这样，就能保证仅对 i ～j 范围内的加数加了 a ，以此配合区间更新时的操作保证所有前缀和的正确性。此处，对加数的处理和原问题（区间更新）处理思路是一样的，给某一区间的所有加数均加 a 的问题实质就是区间更新的问题。因此此处，某一位置 x 的加数不是 lazy_tag[x] 的值，而是 lazy_tag 树状数组的第 x 位置前缀和。
此时，原数据的前缀和与加数的分布为：
理论知识如上，接下来，我将为大家展示代码实现部分，希望可以帮助大家理解本篇文章。如下所示：
今天的分享到此结束，大家如果发现文章中写的不合理的地方，欢迎在下方留言区留言，不胜感激。
没有关注公众号的朋友可以长按下图识别二维码关注公众号了解最新文章。
树状数组求区间最大值(树状数组)(复习)
如题。当遇到单点更新时，树状数组往往比线段树更实用。算法:设原数序列为a[i]，最大值为h[i](树状数组)。1。单点更新：直接更新a[i]，然后再更新h[i]。若h[i]的值有可能改变的，则表示区间一定包含i结点。那么就两层lowbit更... 查看详情
树状数组区间更新(代码片段)
概述这篇文章前半部分主要研究树状数组的区间更新单点求值，后半部分研究区间更新区间求和。前置知识树状数组的基本知识以及单点更新区间求和，差分的思想。区间更新，单点求和分析回顾一下最简单的树状数组的功能：... 查看详情
树状数组区间更新区间查询
1voidins(intk,intx,intt){2for(;x<=tot;x+=x&-x)c[k][x]+=t;3}4llgetsum(intk,intx){5llt=0;for(;x;x-=x&-x)t+=c[k][x];returnt;6}7voidmdy(intx,inty,intz){8ins(0,x,z);ins(1,x,z*(x-1));ins(0,y+1,-z 查看详情
poj3468asimpleproblemwithintegers（树状数组区间更新）
ASimpleProblemwithIntegersTimeLimit:5000MS MemoryLimit:131072KTotalSubmissions:97217 Accepted:30358CaseTimeLimit:2000MSDescriptionYouhaveNintegers,A1,A2,...,AN.Youneedtodealwithtwokindsofope 查看详情
hdu4267asimpleproblemwithintegers（树状数组区间更新）
ASimpleProblemwithIntegersTimeLimit:5000/1500MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):5402 AcceptedSubmission(s):1710Proble 查看详情
树状数组从入门到弃疗(代码片段)
...询区间修改，单点查询区间修改+区间查询区间最值二维树状数组--单点修改，区间查询二维树状数组--区间修改，单点查询二维树状数组--区间修改，区间查询参考资料树状数组是一类存储后缀和，更新后缀和，通过lowbit来限定... 查看详情
51nod_1199树的先跟遍历+区间更新树状数组
...遍历，把整棵树平铺到一维平面中使用自己整的区间更新树状数组模板进行相关操作。http://www.cnblogs.com/rikka/p/7359185.html放代码如下：1#include<bits/stdc++.h>23usingnamespacestd;456/*7*常量MAXN用于设定树状数组的尺寸大小8*/9constlongl 查看详情
1zojp5021asimpleproblemwithinteger2|板子|树状数组的区间更新(代码片段)
树状数组的区间更新思路树状数组的区间更新：首先引入一个差分数组：差分数组：令d[i]=a[i]-a[i-1];a[i]=∑d[i];即可以得到：∑a[k]=d[1]+d[1]+d[2]+d[1]+d[2]+d[3]+...+d[1]+d[2]+d[3]+...+d[k]=∑(k-i+1)*d[i](i从1到k)变化得到：(重要)∑a[k]=∑(k+1)*d[i]-i... 查看详情
树状数组—模板整理
树状数组整理update更新1.单点更新，将第p个数增加v1voidupdate(intp,intv)//将第P个数增加v2{3while(p<=n)4{5sum[p]+=v;6p+=lowbit(p);7}8}2.区间更新，将区间[x,y]增加v1voidinerval_update(intx,inty,intv)//区间修改—[x,y]的区间增加v2{3update(x,v) 查看详情
toj2725seeyou~(二维树状数组单点更新区间查询)(代码片段)
描述NowIamleavinghustacm.Inthepasttwoandhalfyears,IlearnedsomanyknowledgeaboutAlgorithmandProgramming,andImetsomanygoodfriends.IwanttosaysorrytoMr,Yin,Imustleavenow~~>.<~~.Iamverysorry,wecouldnota 查看详情
树状数组区间更新区间查询以及gcd的logn性质
题目描述给你一个长为n的序列am次查询每次查询一个区间的所有子区间的gcd的和mod1e9+7的结果输入描述:第一行两个数n,m之后一行n个数表示a之后m行每行两个数l,r表示查询的区间输出描述:对于每个询问，输出一行一个数表示答案... 查看详情
树状数组基本模版(区间更新，单点查询)
题目描述如题，已知一个数列，你需要进行下面两种操作：1.将某区间每一个数数加上x2.求出某一个数的和输入输出格式输入格式：第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分... 查看详情
hdu4325离散化+树状数组或者不使用树状数组(代码片段)
...，我们需要进行区间更新和单点查询，可以考虑线段树与树状数组两种做法，一般的，树状数组是用来维护区间和与单点修改的，那么，如何通过树状数组进行区间更新和单点查询呢，联想到差分数组，差分数组可以在o(1)的时... 查看详情
树状数组区间加+区间查询模板洛谷p3372
虽然说这道题线段树很好做，但毕竟树状数组常数小又好写，所以还是写个模板吧。区间加转为前缀加区间和转为前缀和我们讨论一个1~k的区间加x对于一个前缀和val【i】的影响对于所有k<i的更新，对val[i]的贡献为val[i]+=k*x对... 查看详情
hdu3584树状数组
...点，那么我们可以统计空间的翻转的次数，然后用三维的树状数组即可，但是更新时不能只更新那个点，因为如果这样能的话，能够包括这个区间的大区间因为还没有更新过而和变成了1，那不是我们要的，所以我们将包围这个... 查看详情
poj2155matrix二维树状数组+yy（区间更新，单点查询）(代码片段)
题目链接：http://poj.org/problem?id=2155MatrixTimeLimit: 3000MS MemoryLimit: 65536KTotalSubmissions: 32950 Accepted: 11943DescriptionGivenanN*NmatrixA,whoseelementsareeither0o 查看详情
poj1201树状数组
...变的，所以不用更新答案求当前区间已经取了多少个数用树状数组代码：1#include& 查看详情
hdu2642树状数组
...时候就处理一下，每次问的是X1，Y1到X2，Y2的区间和，而树状数组的和是从1，1开始的，所以总的减去多于的在加上多减去的就OK了#include<stdio.h>#include<stri 查看详情