演算法練習 「GenomicRangeQuery」 （快速計算矩陣內單位總和的方式）

題目和解法...

講義...

一連串長度為Ｘ的數值矩陣，如何知道單位Ｍ和Ｎ之間有不為零的數值？（Ｍ>N，且絕對不小於零或大於等於X，所以Ｍ和Ｎ單位絕對都在矩陣內。）

這其實是個變相計算總和的技巧。
如果把矩陣從頭（最小單位）跑一次迴圈，並且每次都把前一個單位的值和自己做加總，例如「X[A] = X[A] + X[A-1]」，則等到迴圈跑完，這個迴圈的每個單位（i）會變成「從0到i單位的總和」，如果要知道每個單位原本的值，只需要把單位（i）減去單位（i-1）就好。
如果要問「i到j之間單位的數值總和（假設j > i）」，也只需要把單位（j）減去單位（i）就好。

所以如果題目要知道ATCG在基因序列中出現的頻率，那就宣告四個和基因序列等長的矩陣，個別對應到ATCG，每次只要出現相對應的序列，就在那個矩陣單位中加一（X[A]=1)。

如果C[i] = N，而C[i + a] = N+2，這就表示在「i」到「i+a」這中間的單位裡，Ｃ出現了兩次。這個C[i] - C[i+a]如果稱為Ｆ（Ｃ, i, 2)，則按照題目的要求，F(Ａ, i, j）不為0時答案為1，F(C, j, j)不為零時答案為1......