經典演算法題每日演練——第十題樹狀陣列

有一種資料結構是神奇的，神秘的，它展現了位運算與陣列結合的神奇魅力，太牛逼的，它就是樹狀陣列，這種資料結構不是神人是發現不了的。
一：概序
假如我現在有個需求，就是要頻繁的求陣列的前 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 ///