Prefix Sums（前綴和）概念

甚麼是Prefix Sums（前綴和）

當需要快速查詢數組中某一區間的元素和時，Prefix Sums可以幫助我們在O(1)的時間複雜度內進行查詢。

具體做法是先對數組進行預處理，計算出從第一個元素到當前位置的所有元素的和，然後通過兩個元素的前綴和之差來計算出任意區間的元素和。例如，要查詢數組中第i到第j個元素的和，只需要計算sums[j+1] – sums[i]即可。

Prefix Sums通常用於需要頻繁查詢數組中某一區間的元素和的情況，例如在數學、統計學、計算機科學和機器學習等領域中。Prefix Sums的計算可以在預處理的階段中完成，因此可以在之後的查詢中以O(1)的時間複雜度快速地回答各種區間求和問題。

例如，在計算機科學中，Prefix Sums通常用於解決數組中的區間查詢問題，例如求解區間最大子段和、區間平均值、區間中位數等。Prefix Sums還可以用於在數據壓縮、圖像處理和信號處理等領域中，進行離散化、濾波和卷積等操作。

計算出從第一個元素到當前位置的所有元素的和，是因為這樣可以在之後的區間求和操作中，通過兩個元素的前綴和之差來快速計算任意區間的元素和。例如，要查詢數組中第i到第j個元素的和，只需要計算sums[j+1] – sums[i]即可。這樣可以大大降低區間求和操作的時間複雜度，提高算法效率。

Prefix Sums使用時機

在許多需要進行區間求和操作的問題中，Prefix Sums都是一種常用的解決方案。因此，在識別哪些問題需要使用Prefix Sums時，可以考慮以下幾點：

問題是否需要進行區間求和操作：如果問題需要計算數組中某一區間的元素和，那麼Prefix Sums可能是一個合適的解決方案。
數據集的大小：Prefix Sums通常適用於數據集較小的情況下，因為在預處理階段中需要計算每個元素的前綴和，這可能需要額外的空間和時間。
數據是否可以修改：如果數據集可以修改，那麼在每次修改後，需要重新計算前綴和，這可能會影響算法的效率。因此，在這種情況下，需要仔細考慮使用Prefix Sums的適當性。
計算區間求和的頻率：如果需要頻繁地進行區間求和操作，那麼使用Prefix Sums可能比其他方法更有效。

綜合以上幾點，可以初步判斷哪些問題可能需要使用Prefix Sums。在實際應用中，還需要進一步評估和優化算法，以確保其效率和準確性。

使用Binary Indexed Tree來計算前綴和

BIT的基本思想是將原始數組轉換為一個二進制表示的數組，並在其中儲存一些特定位置的前綴和。BIT的建立和查詢操作都可以在O(n log n)的時間複雜度內完成，其中n是數組的長度。BIT的更新操作可以在O(log n)的時間複雜度內完成。

更多詳細介紹: https://yuihuang.com/binary-indexed-tree/

範例題目 – PassingCars

題目連結

https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/

我的第一次解法(javascript)

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    for(var i=0;i<A.length;i++){
        if(A[i] == 0){
            for(var j = i;j<A.length;j++){
                if(A[j] == 1){
                    current_sum++
                }
            }
        }
    }
    return current_sum
}

成績如下，雖然答案是正確的，但是效率不夠，為O(N**2)，只拿到70%的分數

改善方向

我發現if(A[j] == 1)和if(A[i] == 0)這段其實重複跑了，其實可能在之前的檢查中早就會知道有那些是1哪些是0，重複遍歷是不必要的，因此我決定嘗試用另外的陣列來儲存index為1的index值(value_1_index)和index為0的index(value_0_index)

接下來因為 0 ≤ P < Q < N，所以我們會需要找value_1_index裡面的key值大於value_0_index的，所以會使用var j = value_1_index.findIndex(x=>x>value_0_index[i])來找尋。

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    var value_1_index = [], value_0_index = []
    for(var i=0;i<A.length;i++){
        if(A[i] == 0) value_0_index.push(i)
        else value_1_index.push(i)
    }
    for(var i=0;i<value_0_index.length;i++){
        var j = value_1_index.findIndex(x=>x>value_0_index[i])
        if(j >= 0){
            while(j < value_1_index.length){
                j++
                current_sum++
            }
        }
    }
    return current_sum
}

結果也太哭了，居然沒省多少XD只多了一個勾勾

Detected time complexity:O(N ** 2)

接著我發現這句話!!

The function should return −1 if the number of pairs of passing cars exceeds 1,000,000,000.

因此我決定加上if(current_sum > 1000000000){ return -1 }的判斷在current_sum ++的後面，但結果仍然一樣，但是可以發現至少程式有跑完(不是顯示Killed)，只是速度達不到標準，尤其是large_random和large_alternate差異很大，我的程式跑了5.336秒，要求卻是0.304秒，差了10倍以上(汗顏)。仔細觀察了一下，我個人覺得在large_alternate的題目代表是0和1頻繁交替的狀況下，我的演算法的效能會很差。

因此我猜測這個效能瓶頸和var j = value_1_index.findIndex(x=>x>value_0_index[i])這個搜尋的動作有關，我決定改成當i和j用完就把用完的部分砍掉，以減少搜尋量。為此，我必須把for迴圈改成while，並且讓value_0_index與value_1_index都能隨著時間變小。

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    var value_1_index = [], value_0_index = []
    for(var i=0;i<A.length;i++){
        if(A[i] == 0) value_0_index.push(i)
        else value_1_index.push(i)
    }
    while(value_0_index.length > 0){
        var j = value_1_index.findIndex(x=>x>value_0_index[0])
        if(j >= 0){
            value_1_index = value_1_index.slice(j,value_1_index.length)
            var pointer = 0
            while(pointer < value_1_index.length){
                pointer++
                current_sum++
                if(current_sum > 1000000000){
                    return -1
                }
            }
        }
        value_0_index.shift();
    }
    return current_sum
}

所以問題是出在value_1_index = value_1_index.slice(j,value_1_index.length)這邊太耗時，尤其是最後一項，可以看出是在當某個數字多的時候會更耗時。在這邊我嘗試把slice改成splice，並且在j>0時才去做

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    var value_1_index = [], value_0_index = []
    for(var i=0;i<A.length;i++){
        if(A[i] == 0) value_0_index.push(i)
        else value_1_index.push(i)
    }
    while(value_0_index.length > 0){
        var j = value_1_index.findIndex(x=>x>value_0_index[0])
        if(j >= 0){
            if(j > 0){
                value_1_index.splice(0,j)
            }
            var pointer = 0
            while(pointer < value_1_index.length){
                pointer++
                current_sum++
                if(current_sum > 1000000000){
                    return -1
                }
            }
        }
        value_0_index.shift();
    }
    return current_sum
}

結果有改善，但仍需努力

接著我發現，等等…value_1_index好像不用刪啊!!先決定不要先搜尋好了，把條件設定成從最後一個value_1_index去找起，找到value_1_index裡的值小於value_0_index[0]時停止

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    var value_1_index = [], value_0_index = []
    for(var i=0;i<A.length;i++){
        if(A[i] == 0) value_0_index.push(i)
        else value_1_index.push(i)
    }
    while(value_0_index.length > 0){
        var point = value_1_index.length-1
        while(value_1_index[point] > value_0_index[0]){
            current_sum++
            point--
        }
        value_0_index.shift();
    }
    return (current_sum > 1000000000) ? -1 : current_sum 
}

結果仍然超時，我發現似乎value_0_index也可以不用刪，改回使用for迴圈看看

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    var value_1_index = [], value_0_index = []
    for(var i=0;i<A.length;i++){
        if(A[i] == 0) value_0_index.push(i)
        else value_1_index.push(i)
    }
    for(var i=0;i<value_0_index.length;i++){
        var pointer = value_1_index.length-1
        while(value_1_index[pointer] > value_0_index[i]){
            current_sum++
            pointer  --
        }
    }
    return (current_sum > 1000000000) ? -1 : current_sum 
}

繞了這麼久，我覺得最大的問題應該是在 (0, 1), (0, 3), (0, 4), (2, 3), (2, 4)中， (2, 3), (2, 4)中的3,4其實是(0, 1), (0, 3), (0, 4)中的1,3,4的子集合，所以應該是要做暫存，把第一次的集合儲存起來，之後直接減掉A[0] = 0 A[1] = 1 A[2] = 0之中兩個0中間的1這個值然後加上去就可以了

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    var value_1_index = [], value_0_index = []
    //紀錄兩個0中間經過的1
    var value_0_interval = []
    for(var i=0;i<A.length;i++){
        if(A[i] == 0) {
            value_0_index.push(i)
            value_0_interval[value_0_index.length-1] = 0
        }else {
            value_1_index.push(i)
            value_0_interval[value_0_index.length-1]++
        }
    }
    var current_value_1 = value_1_index.length
    for(var i=0;i<value_0_index.length;i++){
        current_sum = current_sum + current_value_1
        current_value_1 = current_value_1 - value_0_interval[i]
    }
    return (current_sum > 1000000000) ? -1 : current_sum 
}

好…90%，快過了，一開始就要除去第一個value_0_index之前的value_1_index

function solution(A) {
    // Implement your solution here
    var current_sum = 0
    var value_1_index = [], value_0_index = []
    //紀錄兩個0中間經過的1
    var value_0_interval = []
    for(var i=A.indexOf(0);i<A.length;i++){
        if(A[i] == 0) {
            value_0_index.push(i)
            value_0_interval[value_0_index.length-1] = 0
        }else {
            value_1_index.push(i)
            value_0_interval[value_0_index.length-1]++
        }
    }
    var current_value_1 = value_1_index.length
    for(var i=0;i<value_0_index.length;i++){
        current_sum = current_sum + current_value_1
        current_value_1 = current_value_1 - value_0_interval[i]
    }
    return (current_sum > 1000000000) ? -1 : current_sum 
}

終於100%了….https://app.codility.com/demo/results/trainingWK5QAP-PP8/

結論，一個easy程度的我玩這麼多次，真的很哭…但滿好玩的(有嗎?)

Claire's Blog