Posted on

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時,可以考慮以下幾點:

  1. 問題是否需要進行區間求和操作:如果問題需要計算數組中某一區間的元素和,那麼Prefix Sums可能是一個合適的解決方案。
  2. 數據集的大小:Prefix Sums通常適用於數據集較小的情況下,因為在預處理階段中需要計算每個元素的前綴和,這可能需要額外的空間和時間。
  3. 數據是否可以修改:如果數據集可以修改,那麼在每次修改後,需要重新計算前綴和,這可能會影響算法的效率。因此,在這種情況下,需要仔細考慮使用Prefix Sums的適當性。
  4. 計算區間求和的頻率:如果需要頻繁地進行區間求和操作,那麼使用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程度的我玩這麼多次,真的很哭…但滿好玩的(有嗎?)