经典演算法题每日演练——第十题树状阵列

有一种资料结构是神奇的，神秘的，它展现了位运算与阵列结合的神奇魅力，太牛逼的，它就是树状阵列，这种资料结构不是神人是发现不了的。
一：概序
假如我现在有个需求，就是要频繁的求阵列的前 n 项和，并且存在著阵列中某些数字的频繁修改，那么我们该如何实现这样的需求？当然大家可以往
真实专案上靠一靠。
① 传统方法：根据索引修改为 O(1)，但是求前 n 项和为 O(n) 。
②空间换时间方法：我开一个阵列 sum[]，sum[i]=a[1]+….+a[i]，那么有点意思，求 n 项和为 O(1)，但是修改却成了 O(N)，这是因为我的 Sum[i] 中牵
涉的资料太多了，那么问题来了，我能不能在相应的 sum[i] 中只储存某些 a[i] 的值呢？好吧，下面我们看张图。

从图中我们可以看到 S[] 的分布变成了一颗树，有意思吧，下面我们看看 S[i] 中到底存放著哪些 a[i] 的值。
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];
之所以采用这样的分布方式，是因为我们使用的是这样的一个公式：S[i]=a[i-2k+1]+….+a[i] 。
其中：2k 中的 k 表示当前 S[i] 在树中的层数，它的值就是 i 的二进位制中末尾连续 0 的个数，2k 也就是表示 S[i] 中包含了哪些 a[]，
举个例子: i=610=01102 ；可以发现末尾连续的 0 有一个，即 k=1，则说明 S[6] 是在树中的第二层，并且 S[6] 中有 21 项，随后我们求出了起始项：
a[6-21+1]=a[5]，但是在编码中求出 k 的值还是有点麻烦的，所以我们采用更灵巧的 Lowbit 技术，即：2k=i&-i 。
则：S[6]=a[6-21+1]=a[6-(6&-6)+1]=a[5]+a[6] 。
二：程式码
1: 神奇的 Lowbit 函式

1 #region 当前的 sum 数列的起始下标
2 ///

3 /// 当前的 sum 数列的起始下标
4 ///

5 /// 6 ///
7 public static int Lowbit(int i)
8 {
9 return i & -i;
10 }
11 #endregion

2: 求前 n 项和
比如上图中，如何求 Sum(6)，很显然 Sum(6)=S4+S6，那么如何寻找 S4 呢？即找到 6 以前的所有最大子树，很显然这个求和的复杂度为 logN 。

1 #region 求前 n 项和
2 ///

3 /// 求前 n 项和
4 ///

5 /// 6 ///
7 public static int Sum(int x)
8 {
9 int ans = 0;
10
11 var i = x;
12
13 while (i > 0)
14 {
15 ans += sumArray[i – 1];
16
17 //当前项的最大子树
18 i -= Lowbit(i);
19 }
20
21 return ans;
22 }
23 #endregion

3：修改
如上图中，如果我修改了 a[5] 的值，那么包含 a[5] 的 S[5]，S[6]，S[8] 的区间值都需要同步修改, 我们看到只要沿著 S[5] 一直回溯到根即可，
同样它的时间复杂度也为 logN 。

1 public static void Modify(int x, int newValue)
2 {
3 //拿出原阵列的值
4 var oldValue = arr[x];
5
6 for (int i = x; i < arr.Length; i += Lowbit(i + 1)) 7 { 8 //减去老值，换一个新值 9 sumArray[i] = sumArray[i] - oldValue + newValue; 10 } 11 } 最后上总的程式码: View Code 1 using System; 2 using System.Collections.Generic; 3 using System.Linq; 4 using System.Text; 5 using System.Diagnostics; 6 using System.Threading; 7 using System.IO; 8 9 namespace ConsoleApplication2 10 { 11 public class Program 12 { 13 static int[] sumArray = new int[8]; 14 15 static int[] arr = new int[8]; 16 17 public static void Main() 18 { 19 Init(); 20 21 Console.WriteLine("A 阵列的值:{0}", string.Join(",", arr)); 22 Console.WriteLine("S 阵列的值:{0}", string.Join(",", sumArray)); 23 24 Console.WriteLine("修改 A[1] 的值为 3"); 25 Modify(1, 3); 26 27 Console.WriteLine("A 阵列的值:{0}", string.Join(",", arr)); 28 Console.WriteLine("S 阵列的值:{0}", string.Join(",", sumArray)); 29 30 Console.Read(); 31 } 32 33 #region 初始化两个阵列 34 ///

35 /// 初始化两个阵列
36 ///

37 public static void Init()
38 {
39 for (int i = 1; i <= 8; i++) 40 { 41 arr[i - 1] = i; 42 43 //设定其实座标：i=1 开始 44 int start = (i - Lowbit(i)); 45 46 var sum = 0; 47 48 while (start < i) 49 { 50 sum += arr[start]; 51 52 start++; 53 } 54 55 sumArray[i - 1] = sum; 56 } 57 } 58 #endregion 59 60 public static void Modify(int x, int newValue) 61 { 62 //拿出原阵列的值 63 var oldValue = arr[x]; 64 65 arr[x] = newValue; 66 67 for (int i = x; i < arr.Length; i += Lowbit(i + 1)) 68 { 69 //减去老值，换一个新值 70 sumArray[i] = sumArray[i] - oldValue + newValue; 71 } 72 } 73 74 #region 求前 n 项和 75 ///

76 /// 求前 n 项和
77 ///

78 /// 79 ///
80 public static int Sum(int x)
81 {
82 int ans = 0;
83
84 var i = x;
85
86 while (i > 0)
87 {
88 ans += sumArray[i – 1];
89
90 //当前项的最大子树
91 i -= Lowbit(i);
92 }
93
94 return ans;
95 }
96 #endregion
97
98 #region 当前的 sum 数列的起始下标
99 ///