下载文档原格式
树状数组及其应用(Binary Indexed Trees)一、什么是树状数组【引例】假设有一列数{A i}（1<=i<=n），支持如下两种操作：1.将A k的值加D。
（k，D是输入的数）2.输出A s+A s+1+…+A t（s，t都是输入的数，s<=t）分析一：线段树建立一颗线段树（线段长度1~n）。
一开始所有结点的count值等于0。
对于操作1，如果把A k的值加D，则把所有覆盖了A k的线段的count值加D。
只有log2n 条线段会受到影响，因此时间复杂度是O（log2n）。
每条线段[x..y]的count值实际上就是A x+A x+1+…+A y的值。
对于操作2，实际上就是把[s..t]这条线段分解成为线段树中的结点线段，然后把所有的结点线段的count值相加。
该操作（ADD操作）在上一讲线段树中已介绍。
时间复杂度为O （log2n）。
分析二：树状数组树状数组是一种特殊的数据结构，这种数据结构的时空复杂度和线段树相似，但是它的系数要小得多。
增加数组C，其中C[i]=a[i-2^k+1]+……+a[i](k为i在二进制形式下末尾0的个数)。
由c数组的定义可以得出：i K1(1)201-2^0+1=1…1c[1]=a[1]2(10)212-2^1+1=1…2c[2]=a[1]+a[2]=c[1]+a[2]3(11)203-2^0+1=3…3c[3]=a[3]4(100)224-2^2+1=1…4c[4]=a[1]+a[2]+a[3]+a[4]=c[2]+c[3]+a[4] 5(101)205-2^0+1=5…5c[5]=a[5]6(110)216-2^1+1=5…6c[6]=a[5]+a[6]=c[5]+a[6]………………为了对树状数组有个形象的认识，我们先看下面这张图。
如图所示，红色矩形表示的数组C[]就是树状数组。
我们也不难发现，这个k就是该节点在树中的高度，因而这个树的高度不会超过logn。
树状数组简单易懂的详解1 什么是树状数组树状数组（Fenwick Tree），也叫做树形数组，是一种支持单点修改、区间查询的数据结构。
这种数据结构可以在O(log n)的时间复杂度内实现单点修改和区间查询，相较于线段树，树状数组实现较为简单。
2 树状数组的实现原理树状数组的核心思想是利用二进制中的位运算来维护前缀区间和。
假设有一个数组a[]，其前缀和为sum[]，那么对于每个下标i，只需要维护[1,i]这个区间的和，即sum[i]。
这样，当需要查询区间[1,r]的和时，只需要计算sum[r]即可，不需要遍历每一个元素。
对于单点修改操作，假设我们要将数组a[]的第i个元素修改为x，我们只需要将第i个元素的值改为x，并且要将[1,i]这个区间内所有的sum数组的值都加上x-a[i]，即将差值x-a[i]加到了[1,i]区间中。
3 树状数组的实现细节3.1 树状数组的初始化树状数组需要初始化为0，因为我们需要维护的是每个元素的前缀和，如果没有初始化为0，其前缀和也就变得不可预测了。
查询区间[1,r]的和时，只需要计算sum[r]即可。
具体实现过程为：从r开始向前跳，每一个位置的前缀和都加到一个答案变量ans中，直到跳到0为止。
可以使用以下的代码实现：```C++int query(int x){int ans = 0;while(x > 0){ans += tree[x];x -= lowbit(x);}return ans;}```修改操作也很简单，只需要将第i个位置的值改为x，然后将[1,i]这个区间内所有的sum数组的值都加上x-a[i]，即将差值x-a[i]加到了[1,i]区间中，可以使用以下的代码实现：```C++void update(int x, int val){while(x <= n){tree[x] += val;x += lowbit(x);}}```4 树状数组与线段树的比较相对于线段树，树状数组的实现更为简单，而且更加省空间。
[数据结构]树状数组专题做数据结构的题真是异常的能让人感到自己在脱菜的路上迈进啊。
这一次来看看树状数组。
树状数组的基本知识已经被各种大牛和菜鸟讲到烂了，我就不多说了，下面给出基本操作的代码。
假定原数组为a[1..n]，树状数组b[1..n]，考虑灵活性的需要，代码使用int *a传数组。
#define lowbit(x) ((x)&(-(x)))int sum(int *a,int x){int s=0;for(;x;x-=lowbit(x))s+=a[x];return s;}void update(int *a,int x,int w){for(;x<=n;x+=lowbit(x))a[x]+=w;}sum(x)返回原数组[1,x]的区间和，update(x,w)将原数组下标为x的数加上w。
这两个函数使用O(logn)的时间和O(n)的空间完成单点加减，区间求和的功能。
接下来做一些升级，让树状数组完成区间加减，单点查询的功能。
考虑将原数组差分，令d[i]=a[i]-a[i-1]，特别地，d[1]=a[1]。
那么区间[l,r]整体加上k的操作就可以简单地使用d[l]+=k;d[r+1]-=k来完成了。
此时a[i]=d[1]+..+d[i]，所以单点查询a[i]实际上就是在求d数组的[1..i]区间和，很容易完成了。
下面再升级一次，完成区间加减，区间求和的功能。
仍然沿用d数组，考虑a数组[1,x]区间和的计算。
d[1]被累加了x次，d[2]被累加了x-1次，...，d[x]被累加了1次。
因此得到sigma(a[i])=sigma{d[i]*(x-i+1)}=sigma{ d[i]*(x+1) -d[i]*i }=(x+1)*sigma(d[i])-sigma(d[i]*i)所以我们再用树状数组维护一个数组d2[i]=d[i]*i，即可完成任务。
POJ 3468就是这个功能的裸题...下面给出代码：// POJ 3468 Using BIT#include <cstdio>const int fin=0,maxn=100010;__int64 a[maxn],b[maxn],c[maxn];int n,m;inline int lowbit(const int &x){return x&(-x);}__int64 query(__int64 *a,int x){__int64 sum=0;while(x){sum+=a[x];x-=lowbit(x);}return sum;}void update(__int64 *a,int x,__int64 w){ while(x<=n){a[x]+=w;x+=lowbit(x);} }int main(){int l,r,i;__int64 ans,w;char ch;if(fin){freopen("t.in","r",stdin);freopen("t.out","w",stdout);}scanf("%d%d",&n,&m);a[0]=0;for(i=1;i<=n;++i){scanf("%I64d",&a[i]);a[i]+=a[i-1];}while(m--){scanf("%c",&ch);while(ch!='Q' && ch!='C')scanf("%c",&ch);if(ch=='Q'){scanf("%d%d",&l,&r);ans=a[r]-a[l-1]+(r+1)*query(b,r)-l*query(b,l-1)-query(c,r)+query(c,l-1);printf("%I64d\n",ans);}else{scanf("%d%d%I64d",&l,&r,&w);update(b,l,w);update(b,r+1,-w);update(c,l,w*l);update(c,r+1,-(r+1)*w);}}if(fin){fclose(stdin); fclose(stdout);}return 0;}====================================一维到二维的分割线=======================================接下来到二维树状数组。
树状数组的操作树状数组的⼀些基本操作。
树状数组⽀持单点修改和查询区间和的操作，但和线段树不同，它不⽀持区间修改操作（有些题⽬可以将区间修改转化为单点修改，有些则不可以）。
下⾯介绍树状数组的预处理和基本操作。
1.求lowbit(n)上⼀篇博客介绍了lowbit的定义和使⽤定义的基本求法。
但是依据定义求lowbit未免⿇烦。
因⽽，求lowbit需要导⼊公式：lowbit(n)=n&(-n)。
求lowbit函数：int lowbit(int n){//求n的lowbitreturn n&(-n);}2.对某个元素进⾏加法操作根据树状数组的性质，对于任意⼀个结点x，只有结点c[x]及其祖先结点保存的区间和中含a[x]，所以我们只需要对x不断向上搜索即可。
代码：void update(int x,int y){//将x位置元素加上yfor(;x<=N;x+=lowbit(x){//依次寻找x的⽗节点c[x]+=y;//进⾏更新}}这⾥在寻找x的⽗节点时运⽤了上⼀篇博客中的性质③（具体的证明⽅法我也不会qwq）。
举例证明：假设我们要对A[2]进⾏加x的操作。
2的lowbit值为2，则第⼀步2变成了4，对C[4]进⾏处理。
4的lowbit值为4，则第⼆步变成了8，对C[8]进⾏处理。
此时已到达循环边界。
再假设我们要对A[5]进⾏加x的操作。
5的lowbit值为1，则第⼀步5变成了6，对C[6]进⾏处理。
6的lowbit值为2，则第⼆步变成了8，对C[8]进⾏处理。
此时已到达循环边界。
3.查询前缀和操作前缀和的求法：求出x的⼆进制表⽰中每个等于1的位，把[1,x]分成logN个⼩区间，⽽每个⼩区间的区间和已保存在数组c中。
代码（我也不会证）：int sum(int x){//求1~x的区间和int ans=0;for(;x;x-=lowbit(x);){ans+=c[x];}return ans;}举例证明：假设我们要求A[6]的前缀和。
第01讲什么是树状数组？树状数组用来求区间元素和，求一次区间元素和的时间效率为O(logn)。
有些同学会觉得很奇怪。
用一个数组S[i]保存序列A[]的前i个元素和，那么求区间i,j的元素和不就为S[j]-S[i-1]，那么时间效率为O(1)，岂不是更快？但是，如果题目的A[]会改变呢？例如：我们来定义下列问题：我们有n个盒子。
可能的操作为1.向盒子k添加石块2.查询从盒子i到盒子j总的石块数自然的解法带有对操作1为O(1)而对操作2为O(n)的时间复杂度。
但是用树状数组，对操作1和2的时间复杂度都为O(logn)。
第02讲图解树状数组C[]现在来说明下树状数组是什么东西？假设序列为A[1]~A[8]网络上面都有这个图，但是我将这个图做了2点改进。
（1）图中有一棵满二叉树，满二叉树的每一个结点对应A[]中的一个元素。
（2）C[i]为A[i]对应的那一列的最高的节点。
现在告诉你：序列C[]就是树状数组。
那么C[]如何求得？C[1]=A[1];C[2]=A[1]+A[2];C[3]=A[3];C[4]=A[1]+A[2]+A[3]+A[4];C[5]=A[5];C[6]=A[5]+A[6];C[7]=A[7];C[8]= A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8];以上只是枚举了所有的情况，那么推广到一般情况，得到一个C[i]的抽象定义：因为A[]中的每个元素对应满二叉树的每个叶子，所以我们干脆把A[]中的每个元素当成叶子，那么：C[i]=C[i]的所有叶子的和。
现在不得不引出关于二进制的一个规律：先仔细看下图：将十进制化成二进制，然后观察这些二进制数最右边1的位置：1 --> 000000012 --> 000000103 --> 000000114 --> 000001005 --> 000001016 --> 000001107 --> 000001118 --> 000010001的位置其实从我画的满二叉树中就可以看出来。
树状数组和线段树-电脑资料一、树状数组在解题过程中，我们有时需要维护一个数组的前缀和S[i]=A[1]+A[2]+...+A[i]，实现：对于正整数x，定义lowbit（x）为x的二进制表达式中最右边的1所对应的值。
Lowbit(x)=xand-x对于节点i，如果它是左子节点，其父节点为i+lowbit(i)；构造一个辅助数组C，其中Ci=Ai-lowbit(i)+1+Ai-lowbit(i)+2+…+Ai即C的每个元素都是A数组中的一段连续和。
具体是每个灰色节点i都属于一个以它自身结尾的水平长条，这个长条中的数之和就是Ci。
如C12=A9+A10+A11+A12=C10+A11+A12如何更新C数组中的元素：如果修改了一个Ai，需要更新C数组中的哪些元素呢？从Ci开始往右走，边走边“往上爬”（不一定沿着树中的边爬），沿途修改所有结点对应的Ci即可。
预处理时先把C数组清空，然后执行n次add操作。
总时间为O（nlogn）如何计算前缀和Si：顺着结点i往左走，边走边“往上爬”（不一定沿着树中的边爬），把沿途经过的Ci累加起来就可以了。
对于query（L,R）=SR-SL-1。
代码：varb,c,f:array[0..100000]oflongint;ff,a:Array[0..100000]ofboolean; i,j,m,n,x,y,ans,l,r,tmp:longint; s:string;functiondfs(x:longint):longint; beginifx<=1thenexit;c[f[x]]:=c[f[x]]+c[x];dfs(f[x]);end;proceduredfs1(x:longint);begindec(c[x]);ifx<=1thenexit;dfs1(f[x]);end;proceduredfs2(x:longint);begininc(c[x]);ifx<=1thenexit;dfs2(f[x]);beginreadln(n);fillchar(ff,sizeof(ff),true); fori:=1ton-1dobeginreadln(x,y);f[y]:=x;inc(b[x]);end;fori:=1tondoc[i]:=1;fori:=1tondobeginifb[i]=0thendfs(i);end;readln(m);fori:=1tomdobeginx:=0;readln(s);ifs[1]='Q'thenforj:=3tolength(s)dox:=x*10+ord(s[j])-ord('0');writeln(c[x]);end;ifs[1]='C'thenbeginforj:=3tolength(s)dox:=x*10+ord(s[j])-ord('0');ifff[x]thendfs1(x)elsedfs2(x);ff[x]:=notff[x];end;end;End.二、线段树1,.线段树的结构:区间：用一对数a和b表示一个前闭后开的区间[a,b)。
树状数组是一个查询和修改复杂度都为log(n)的数据结构，假设数组a[1..n]，那么查询a[1]+...+a[n]的时间是log级别的，而且是一个在线的数据结构，支持随时修改某个元素的值，复杂度也为log级别。
来观察这个图：令这棵树的结点编号为C1，。
令每个结点的值为这棵树的值的总和，那么容易发现：C1 = A1C2 = A1 + A2C3 = A3 C4 = A1 + A2 + A3 + A4C5 = A5C6 = A5 + A6C7 = A7C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8...C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16这里有一个有趣的性质：设节点编号为x，那么这个节点管辖的区间为2^k（其中k为x二进制末尾0的个数）个元素。
因为这个区间最后一个元素必然为Ax，所以很明显：Cn = A(n –2^k + 1) + ... + An算这个2^k有一个快捷的办法，定义一个函数如下即可：int lowbit(int x){return x&(x^(x–1));}当想要查询一个SUM(n)(求a[n]的和），可以依据如下算法即可：step1:令sum = 0，转第二步；step2:假如n <= 0，算法结束，返回sum值，否则sum = sum + Cn，转第三步；step3: 令n = n –lowbit(n)，转第二步。
可以看出，这个算法就是将这一个个区间的和全部加起来，为什么是效率是log(n)的呢？以下给出证明：n = n –lowbit(n)这一步实际上等价于将n的二进制的最后一个1减去。
而n的二进制里最多有log(n)个1，所以查询效率是log(n)的。
那么修改呢，修改一个节点，必须修改其所有祖先，最坏情况下为修改第一个元素，最多有log(n)的祖先。
树状数组failedbamboo@维护前缀和•包含n个元素的整数数组A，每次可以–C(i, j): 修改一个元素A[i] = j–Q(i): 询问前缀S i=A1+A2+…+A i的值•如何设计算法，使得修改和询问操作的时间复杂度尽量低？例1. 手机(IOI2001)•Tampere地区被划分成N*N个单元，形成一个N*N的表格，行列坐标均为0到N-1，每个单元中有一个移动电话信号发射基地–C(X,Y,A): 基地(X,Y)移动电话数的变化A–Q(L,T,R,B): 询问矩形区域内移动电话总数•注意C操作中A可正可负分析•任意矩形转化为四个前缀矩形•转化为二维前缀和•二维独立, 分别处理, 每次操作log2n例2. 01矩阵•给n*n的01矩阵,支持–C(x0,y0,x1,y1)：改变矩形（每个元素取反）–Q(x,y)：查询(x,y)的值分析•构造辅助01矩阵C’，初始为0•矩形分解: C(x 0,y 0,x 1,y 1)等价为改变以下4点的值–C’(x 0,y 0), C’(x 0,y 1), C’(x 1,y 0), C’(x 1,y 1)•元素(x,y)的最终值完全取决于在C’中(x,y)的右下方的元素和的奇偶性•维护二维前缀和Æ二维数状数组例3. 方格问题•在一个N*N格点方阵的给了一些长度为1的线段, 每条线段的格式为(X , Y , D), 其中D 可以是H（往右）或者V（往下）•计算出一共有多少个正方形。
上图共有3个正方形，两个边长为1，一个边长为2分析•用一个01矩阵表示每条元线段是否存在•算法一:然后枚举左上角顶点和边长，检查每条元线段是否都存在。
时间复杂度O(n4)•算法二:预处理计算出每个点往下，往右可以延伸多长，判断整条边降为O(1)，总时间降为O(n3)•设左上角为(x, y), 若存在边长为K的正方形–不一定存在K-1的正方形–但是我们至少可以确定，K-1正方形的其中两条边是必然存在的算法•依次处理各条斜线, 每条线自左上到右下依次考虑各个点–累加新点往左上方向“作用范围”内的点数–删除往右下方向已经延伸不到当前位置的点•用树状数组维护连续和，O(n2logn)例4. 队伍选择(Balkan 2004)•IOI要来了，BP队要选择最好的选手去参加。
树状数组的算法原理宝子！今天咱来唠唠树状数组这个超酷的东西。
树状数组啊，就像是一个魔法小助手，能帮我们快速解决好多关于数组的问题呢。
你想啊，要是有一个长长的数组，里面有好多好多数字，我们要对它做一些统计操作，比如说求某个区间的和之类的，要是用普通的方法，那可就太麻烦啦。
咱先说说树状数组的结构。
它看起来有点像一棵树，但又不是那种特别复杂的树。
它的每个节点都和数组里的元素有着神秘的联系。
你可以把它想象成是一群小精灵在守护着数组。
这些小精灵们可不是乱站的，它们有着自己独特的排列方式。
比如说，对于一个普通的数组，树状数组的节点是怎么对应的呢？树状数组的每个节点实际上是对应着原数组的一段区间。
这就很神奇啦，就好像每个小精灵都负责看守数组里的一块小天地。
而且呢，这些区间还有重叠的部分，就像小精灵们的地盘有时候会有交叉一样。
那它是怎么构建的呢？这就像是搭积木一样。
我们从最基础的元素开始，一点点地构建出这个树状结构。
最开始的时候，每个元素就像是一个小种子，然后随着构建的过程，它们慢慢组合起来，形成更大的节点。
这个过程其实并不复杂，只要按照一定的规则，就像按照一个小魔法咒语一样，就能轻松构建出来。
再说说它的查询操作。
这可是树状数组的拿手好戏。
当我们想要知道某个区间的和的时候，树状数组就像一个超级计算器一样，迅速给出答案。
它不是傻乎乎地一个一个数字去加哦，而是利用它的树状结构，巧妙地跳跃式计算。
就好比我们要找从第3个元素到第7个元素的和，树状数组不会从3加到7，而是根据它的节点关系，快速地找到对应的几个节点，把它们的值加起来就好啦。
这速度，就像闪电一样快。
还有更新操作呢。
如果我们改变了原数组里的一个元素的值，树状数组也能很快地做出调整。
它不会把整个树状结构都重新构建一遍，而是像一个聪明的小工匠，只对受到影响的部分进行修改。
这就像在一个大城堡里，有一块小砖头坏了，工匠只需要修补那一块，而不是把整个城堡都拆了重建。
树状数组在很多实际的问题里都特别有用。
树状数组先看一个简单的例子：例一：一个学校有ｎ个班级，起初每个班级都没有学生，学校的招生办遇到了一个棘手的问题，他们必须随时了解前ｎ个班级的总人数（任务一），并且随时会增加若干人到某一个班级（任务二）。
我们可以很容易的想到一个简单的算法，开一个长度为ｎ的一位数组记录每个班的人数，这样完成任务二的时间复杂度是ｏ（１），但是完成任务一的时间复杂度是ｏ（ｎ），所以速度较慢。
我们也可以用ａ［ｉ］记录前ｉ个班级的总人数，这样完成任务一的时间复杂度是ｏ（１），但是完成任务二的时间复杂度是ｏ（ｎ）。
以上两种方法在ｎ很大的情况下速度都比较慢。
所以我们必须引入新的数据结构——数状数组。
我们同样以例一为例，定义数组ａ，其中ａ［ｉ］表示第ｉ个班级的人数。
再定义一个数组ｃ，其中C[i]=a[i-2k+1]+……+a[i](k为i在二进制形式下末尾0的个数)。
由c数组的定义可以得出：c[1]=a[1]c[2]=a[1]+a[2]=c[1]+a[2]c[3]=a[3]c[4]=a[1]+a[2]+a[3]+a[4]=c[2]+c[3]+a[4]c[5]=a[5]c[6]=a[5]+a[6]=c[5]+a[6]………………如上图所示为ｎ＝９时的情况。
任务一：定理若a[k]所牵动的序列为C[p1]，C[p2]……C[p m]。
则p1=k，而p i+1=p i+2li（l i为p i在二进制中末尾０的个数）。
由此得出更改元素值的方法：若将x添加到a[k]，则c数组中c[p1]、c[p2]、…、c[p m]（p m≤n<p m+1）受其影响，亦应该添加x。
例如a[1]……a[9]中，a[3] 添加x；p1=k=3 p2=3+20=4p3=4+22=8 p4=8+23=16>9由此得出，c[3]、c[4]、c[8]亦应该添加x。
引理若a[k]所牵动的序列为C[p1]，C[p2] …… C[p m]，且p1 <p2 < …… <p m ，则有l1 <l2< …… <l m（l i为p i在二进制中末尾０的个数）。
一搞懂树状数组引用请注明出处：/int64ago/article/details/7429868写下这个标题，其实心里还是没底的，与其说是写博帖，不如说是做总结。
第一个接触树状数组还是两年前，用什么语言来形容当时的感觉呢？……太神奇了！真的，无法表达出那种感觉，她是那么的优雅，10行不到的代码，却把事情干的如此出色！没有了解她原理的前提下即使把代码倒背如流也理解不了！其中，我就是一直没搞懂地在使用她。
时隔两年，又无意遇到了她，可能是两年的代码经验的积累，有了些新的认识，可以自信的说理解了吧！下面我争取用自己的方式让更多人明白她，而不是背诵她。
为了更方便的说明，文章里会自己强加一些概念，只是为了更好的理解，不是什么专业术语之类的。
一、树状数组是干什么的？平常我们会遇到一些对数组进行维护查询的操作，比较常见的如，修改某点的值、求某个区间的和，而这两种恰恰是树状数组的强项！当然，数据规模不大的时候，对于修改某点的值是非常容易的，复杂度是O(1)，但是对于求一个区间的和就要扫一遍了，复杂度是O(N)，如果实时的对数组进行M次修改或求和，最坏的情况下复杂度是O(M*N)，当规模增大后这是划不来的！而树状数组干同样的事复杂度却是O(M*lgN)，别小看这个lg，很大的数一lg就很小了，这个学过数学的都知道吧，不需要我说了。
申明一下，看下面的文章一定不要急，只需要看懂每一步最后自然就懂了。
二、树状数组怎么干的？先看两幅图（网上找的，如果雷同，不要大惊小怪～），下面的说明都是基于这两幅图的，左边的叫A图吧，右边的叫B图：是不是很像一颗树？对，这就是为什么叫树状数组了～先看A图，a数组就是我们要维护和查询的数组，但是其实我们整个过程中根本用不到a数组，你可以把它当作一个摆设！c数组才是我们全程关心和操纵的重心。
先由图来看看c 数组的规则，其中c8 = c4+c6+c7+a8，c6 = c5+a6……先不必纠结怎么做到的，我们只要知道c数组的大致规则即可，很容易知道c8表示a1～a8的和，但是c6却是表示a5～a6的和，为什么会产生这样的区别的呢？或者说发明她的人为什么这样区别对待呢？答案是，这样会使操作更简单！看到这相信有些人就有些感觉了，为什么复杂度被lg了呢？可以看到，c8可以看作a1～a8的左半边和+右半边和，而其中左半边和是确定的c4，右半边其实也是同样的规则把a5～a8一分为二……继续下去都是一分为二直到不能分，可以看看B图。
树状数组简介江苏省常州高级中学曹文一、前言我们平日里总是会遇到一些动态的求和问题，一些朴素的方法时间速度上很难让人满意，因此我们需要设计一些算法来解决所遇到的问题。
1、 基本问题我们下面设法解决这个动态求和问题。
我们定义 N 个整型变量组成的数组 v[1..N]，每次操作有两种：（1） 将v[idx] 增加 det（2） 求 ∑=idxi i v 1][2、 朴素解决朴素的解决这个问题，我们用数组记录当前的数值，然后依次求和。
那么操作（1）的复杂度是 O(1)，操作（2）的复杂度是 O(idx)，令询问数为 Q ，则在最坏情况下为 O(QN)。
这样的复杂度非常不理想，我们要对之优化！二、倍增，分割和优化很多时候在处理区间问题的时候，倍增思想都是非常常用的，比如 RMQ 和LCA 问题，而分割方法也是一个有用的工具，比如线段树。
我们知道线段树是能够解决上面这个基本问题的，但是考虑到线段树的代码比较复杂，这里我们讨论更轻松的方法。
1、 第一个想法我们发现，在朴素算法中，操作（2）用了很多的时间，我们试着优化这个操作的算法。
参照RMQ 的思想，我们可以将一个区间分成一些长度为2的整次幂的小区间。
我们定义f[i][j] 表示区间 [I, i+2^j-1] 的和∑=-+jk k i v 21]1[，那么如果我们能够得到所有 f[i][j] ，那么我们就能够在 O(log N) 的时间里计算出我们需要的和。
具体方法如下：对于区间 [L,R]，我们找到最大的 p ，使得 2^p <= R-L+1，而 sum[L,L+2^p-1] =f[L][p]，于是我们只要继续计算 [L+2^p,R]就可以了。
由于每次找最大的 p，因次至多计算 log N 次就能得到结果——这就是倍增思想的应用。
但是很不幸，我们再观察操作（1）的时候，我们发现由于和某一个位置相关的 f[i][j] 实在太多了，所以操作（1）的时间就花的过多了，问题并没有得到解决。
