有一种数据结构是神奇的，神秘的，它展现了位运算与数组结合的神奇魅力，太????了，它就是树状数组，这种数据结构不是神人是发现不了的。
一:概序假如我现在有个需求，就是要频繁的求数组的前n项和，并且存在着数组中某些数字的频繁修改，那么我们该如何实现这样的需求？当然大家可以往真实项目上靠一靠。
①传统方法：根据索引修改为O(1)，但是求前n项和为O(n)。
②空间换时间方法：我开一个数组sum[]，sum=a[1]+....+a，那么有点意思，求n项和为O(1)，但是修改却成了O(N)，这是因为我的Sum中牵涉的数据太多了，那么问题来了，我能不能在相应的sum中只保存某些a的值呢？好吧，下面我们看张图。
从图中可以看到S[]的分布变成了一颗树，有意思吧，下面我们看看S中到底存放着哪些a的值。
S[1]=a[1];
S[2]=a[1]+a[2];
S[3]=a[3];
S[4]=a[1]+a[2]+a[3]+a[4];
S[5]=a[5];
S[6]=a[5]+a[6];
S[7]=a[7];
S[8]=a[1]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8];
··无奈数学公式不支持，只能截一张图啦··
二:代码1.神奇的Lowbit函数///summary///当前的sum数列的起始下标////summary///paramname="i"/param///returns/returnspublicstaticintLowbit(inti){returni-i;}2:求前n项和
比如上图中，如何求Sum(6)，很显然Sum(6)=S4+S6，那么如何寻找S4呢？即找到6以前的所有最大子树，很显然这个求和的复杂度为logN。
///summary///求前n项和////summary///paramname="x"/param///returns/returnspublicstaticintSum(intx){intans=0;vari=x;while(i0){ans+=sumArray[i-1];//当前项的最大子树i-=Lowbit(i);}returnans;}3：修改
如上图中，如果我修改了a[5]的值，那么包含a[5]的S[5]，S[6]，S[8]的区间值都需要同步修改,我们看到只要沿着S[5]一直回溯到根即可，同样它的时间复杂度也为logN。
publicstaticvoidModify(intx,intnewValue){//拿出原数组的值varoldValue=arr[x];for(inti=x;iarr.Length;i+=Lowbit(i+1)){//减去老值，换一个新值sumArray=sumArray-oldValue+newValue;}}
最后上总的代码:
publicclassProgram{staticint[]sumArray=newint[8];staticint[]arr=newint[8];publicstaticvoidMain(){Init();Console.WriteLine("A数组的值:{0}",string.Join(",",arr));Console.WriteLine("S数组的值:{0}",string.Join(",",sumArray));Console.WriteLine("修改A[1]的值为3");Modify(1,3);Console.WriteLine("A数组的值:{0}",string.Join(",",arr));Console.WriteLine("S数组的值:{0}",string.Join(",",sumArray));Console.Read();}///summary///初始化两个数组////summarypublicstaticvoidInit(){for(inti=1;i=8;i++){arr[i-1]=i;//设置其实坐标：i=1开始intstart=(i-Lowbit(i));varsum=0;while(starti){sum+=arr[start];start++;}sumArray[i-1]=sum;}}publicstaticvoidModify(intx,intnewValue){//拿出原数组的值varoldValue=arr[x];arr[x]=newValue;for(inti=x;iarr.Length;i+=Lowbit(i+1)){//减去老值，换一个新值sumArray=sumArray-oldValue+newValue;}}///summary///求前n项和////summary///paramname="x"/param///returns/returnspublicstaticintSum(intx){intans=0;vari=x;while(i0){ans+=sumArray[i-1];//当前项的最大子树i-=Lowbit(i);}returnans;}///summary///当前的sum数列的起始下标////summary///paramname="i"/param///returns/returnspublicstaticintLowbit(inti){returni-i;}}一线码农聊技术
一杯咖啡通宵写码