树状数组-白红宇

树状数组

阅读量：5740 次

发布时间：2019-06-18

本文共 1905 字，大约阅读时间需要 6 分钟。

最近沉迷文化课，好久没有研究新算法了（也就那么十来天吧，嗯。），而且还有一大堆题都还没订正，趁着现在一点时间就学了一下一个叫做树状数组的基(gao)础(shen)数据结构（是不是觉得我特别菜，嗯，我自己都这么觉得）。好了，不和大家扯淡了，开始正题——树状数组！

树状数组这种东西，感觉功能和线段树差不多（我认为），只是它不能支持区间修改（其实如果线段树不打Lazy tag的也不支持区间修改）。树状数组支持的操作有：1、单点修改 2、区间查询

算法核心思想：

个人认为，其实树状数组的算法核心就是二进制拆分，对于一个数比如13，13的二进制就是1101，那么13= $2^{3}$ + $2^{2}$ + $2^{0}$ ，换个角度看是不是可以把1-13分为三个区间：[1, $2^{3}$ ]，[ $2^{3}$ +1, $2^{3}$ + $2^{2}$ ]，[ $2^{3}$ + $2^{2}$ +1, $2^{3}$ + $2^{2}$ + $2^{0}$ ]，然后一种叫做树状数组的神奇数据结构就诞生啦！！！（鼓掌）树状数组张这样：

这个时候顺着图，假如说，我们要查询[1-7]这一区间应该怎么办呢？

我们知道，7= $2^{2}$ + $2^{1}$ + $2^{0}$ ，也就是说可以分为，[1, $2^{2}$ ]，[ $2^{2}$ +1, $2^{2}$ + $2^{1}$ ]，[ $2^{2}$ + $2^{1}$ +1, $2^{2}$ + $2^{1}$ + $2^{0}$ ] 这三个区间，结合上图就是c[4]，c[6]，c[7]，这仨茬儿，也就是c[ $2^{2}$ ]，c[ $2^{2}$ + $2^{1}$ ]，c[ $2^{2}$ + $2^{1}$ + $2^{0}$ ]。发现了啥？——这TM不就是二进制拆分吗！！！

那么区间[1,5] 呢？c[4]和c[5]呗。[1,6]呢？c[4]和c[6]呗！

就问你这东西简不简单？——简单~~（个毛线啊）~~！！！

关于快速地进行“二进制拆分”

如果我们按照朴素的方式进行二进制拆分，其实会很浪费，因为我们只需要二进制中为“1”的项就可以了，所以在这里给大家介绍一种叫做lowbit的神奇操作：

作用是求二进制中最后的1附带上后面所有0构成的数的数值。

具体操作为：n and (~n+1)=n and (-n) （其中“~”为逐位取反）

那么我们如何来证明这个操作的正确性呢？

首先我们设一个非负整数n在二进制表示下第k位为1，且第k位以后都是0，n=x...xx100...00。

所以n取反后变为n'=x'...x'x'011...11。再加1，n''=x'...x'x'100...00。

最后n and n''=100...00。

另外在补码表示下，~n=-1-n这应该是“常识”吧，就不多提了。（~~我可不会告诉你是因为我也不知道才这么写的~~）

所以有了这个lowbit操作后，我们就可以通过不断的让"x-lowbit(x)"来获取[1,x]在树状数组中所要加的区间了。

关于更新操作

更新操作其实和我们上文一直在讨论的查询操作差不多，可以结合上图——呃，好吧知道你们懒得在往上翻了，那就再插一遍吧。好，我们结合下图，嗯，下图，继续。

这个时候，树状数组这样构造的另一个特征就不得不被提及了——c[x]的父亲结点为c[x+lowbit(x)]，所以就很方便我们对这个树形结构进行更新，只需要递归进行就ok了。

关于查询操作

查询操作其实在我们讲核心思想的时候就把他给讲完了，最后要提的一点就是：我们不能直接求出[L,R]这一区间，而需要通过[1,R]-[1,L-1]来进行。

The End

嗯，上代码吧！！！

1 var 2   a,c:array[0..100000]of longint; 3   n,m,i,x,y,tip:longint; 4 procedure update(x,y:longint); 5 begin 6   while x<=n do 7   begin 8     c[x]:=c[x]+y; 9     x:=x+x and(-x);10   end;11 end;12 function sum(x:longint):longint;13 begin14   sum:=0;15   while x>0 do16   begin17     sum:=sum+c[x];18     x:=x-x and(-x);19   end;20 end;21 begin22   read(n,m);23   for i:=1 to n do24   begin25     read(a[i]);26     update(i,a[i]);27   end;28   for i:=1 to m do29   begin30     read(tip,x,y);31     if tip=1 then update(x,y) else writeln(sum(y)-sum(x-1));32   end;33 end.

转载于:https://www.cnblogs.com/WR-Eternity/p/9723126.html

你可能感兴趣的文章