1.概念定義 1）部分和

部分和就是給定一個一個數(shù)組arr,求其中某一段連續(xù)子數(shù)組[l,r]的和。通常的做法是遍歷l到r之間的元素相加，這樣的作法最壞時間復(fù)雜度可以達(dá)到O(n),如果有m次訪問時間復(fù)雜度達(dá)到了O(mn)。基于對上述問題的優(yōu)化，我們引入前綴和的概念。

2）前綴和

我們可以聲明一個數(shù)組sum，來記錄數(shù)組前i項(xiàng)的和，可以得出遞推公式sum[i]=sum[i-1]+arr[i]。有了遞推公式，我們還要考慮邊界值，即sum[0]的值，由于此時sum[0]=a[0]，可得出sum[-1]=0。由于代碼中下標(biāo)不能為-1，只要做一次i的判斷就可以了。

3）通過前綴和計算部分和

有了sum數(shù)組之后，我們就可以利用差分法，用sum[r]-sum[l-1]即可求出[l,r]區(qū)間內(nèi)所有元素的和，每一次計算時間復(fù)雜度都是O(1)。

2.算法詳解 1)前綴和

例：給定一個整數(shù)數(shù)組num，請計算數(shù)組的中心下標(biāo)。如果數(shù)組有多個中心下標(biāo)，應(yīng)該返回最靠近左邊的那一個。如果數(shù)組不存在中心下標(biāo)，返回-1。中心下標(biāo)是數(shù)組的一個下標(biāo)，其左側(cè)所有元素加起來的和等于右側(cè)所有元素加起來的和。

成都創(chuàng)新互聯(lián)長期為1000+客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對不同對象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為壽縣企業(yè)提供專業(yè)的網(wǎng)站建設(shè)、成都網(wǎng)站建設(shè)，壽縣網(wǎng)站改版等技術(shù)服務(wù)。擁有10多年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。

思想：從左往右枚舉數(shù)組中的元素，計算左側(cè)元素和與右側(cè)元素和，若兩者相等則直接返回下標(biāo)。每次計算時間復(fù)雜度O(1)，總過程為O(n)。代碼實(shí)現(xiàn)如下。

public int pivotIndex(int[] arr){int size = arr.length;
    int[] sum = new int[size];
    //計算前綴和
    for(int i=0;isum[i] = arr[i];
        if(i>0){sum[i] += sum[i-1];
        }
    }
    //判斷邊界值0
    if(sum[0] == sum[size-1]){return 0;
    }
    //遍歷數(shù)組分別計算每一個元素的左側(cè)和和右側(cè)和
    for(int i=1;iif(sum[i-1] == sum[size-1]-sum[i]){return i;
        }
    }
    //找不到中心坐標(biāo)返回-1
    return -1;
}

2）前綴積

例：給定一個整數(shù)數(shù)組num，返回輸出數(shù)組output，其中output[i]為num中除num[i]外所有數(shù)的乘積。

思想：前綴和的變種，求和改為求積即可，同理的還有前綴異或和，即sum[i]=sum[i-1]^a[i]。此題的代碼實(shí)現(xiàn)如下。

public int[] productExceptSelf(int[] arr){int size = arr.length;
    int[] pre = new int[size];
    //計算前綴積
    for(int i=0;ipre[i] = arr[i];
        if(i>0){pre[i] *= pre[i-1];
        }
    }
    //為了方便后續(xù)計算，同時計算出后綴積
    int[] post = new int[size];
    for(int i=size-1;i>=0;i--){post[i] = arr[i];
        if(ipost[i] *= post[i+1];
        }
    }
    int[] result = new int[size];
    //為了計算方便，這里取i-1的前綴積乘i+1的后綴積作為結(jié)果
    for(int i=0;iif(i==0){result[i] = post[i+1];
        }else if(i==size-1){result[i] = pre[i-1];
        }else{result[i] = pre[i-1]*post[i+1];
        }
    }
    return result;
}

3.前綴和統(tǒng)計 1）問題引入

給定一個整數(shù)數(shù)組arr，其初始元素都為0。然后選擇一個區(qū)間[1,5]，給其中每個元素加3；在選擇一個區(qū)間[3,6]，給其中每個元素加2。求此時arr中每個元素的值是多少。

2）樸素算法

假設(shè)數(shù)組長度為n，總共經(jīng)過m次累加操作，如果每次累加都需要遍歷區(qū)間內(nèi)所有元素的話，最壞情況時間復(fù)雜度為O(mn)。

3）優(yōu)化算法

當(dāng)在數(shù)組arr的[l,r]區(qū)間上累加一個數(shù)x時，可以在l位置加x，再在r+1的位置減x，再求前綴和，就是我們要的結(jié)果。此時每次累加操作時間復(fù)雜度為O(1)，整個過程為O(n)。

4.前綴和統(tǒng)計例題

例：這里有n個航班，它們分別從1到n進(jìn)行編號。有一份航班預(yù)定表bookings，表中第i條記錄為bookings[i]=[firsti,lasti,seatsi]，意味著在從firsti到lasti的每個航班，都預(yù)定了seatsi個座位。請你返回一個長度為n的數(shù)組，里面的元素是每個航班預(yù)定的座位總數(shù)。

思想：對每個區(qū)間[firsti,lasti]，我們在firsti的位置加seatsi，在lasti+1的位置減seatsi，最后統(tǒng)計前綴和就是答案。代碼實(shí)現(xiàn)如下。

public int[] cropFlightBookings(int[][] bookings,int n){//初始化一個所有元素都是0的數(shù)組
    int[] sum = new int[n+1];
    //用O(1)的方式操作數(shù)組，使其滿足在區(qū)間[firsti,lasti]上增加seatsi
    for(int i=0;iint first = bookings[i][0];
        int last = bookings[i][1];
        int seats = bookings[i][2];
        sum[first] += seats;
        sum[last+1] -= seats;
    }
    int[] res = new int[n];
    //對數(shù)組sum求前綴和即可求出結(jié)果
    for(int i=1;ires[i-1] = sum[i];
        if(i>1){res[i-1] += res[i-2];
        }
    }
    return res;
}

5.差分?jǐn)?shù)組

上文所講的前綴和統(tǒng)計用的例子都是初始為0的數(shù)組，當(dāng)數(shù)組初始元素不為0則無法進(jìn)行前綴和統(tǒng)計的操作，這種情況下，我們需要自己創(chuàng)造一個數(shù)組d，使它的前綴和sum[i]=arr[i]。根據(jù)前綴和的定義，我們可以遞推出該數(shù)組中的元素d[i]=arr[i]-arr[i-1]。數(shù)組d就叫做arr的差分?jǐn)?shù)組。在數(shù)組d上即可進(jìn)行上述的前綴和統(tǒng)計操作。

習(xí)題

1894. 找到需要補(bǔ)充粉筆的學(xué)生編號

2256. 最小平均差

1737. 滿足三條件之一需改變的最少字符數(shù)

2055. 蠟燭之間的盤子

文章內(nèi)容為英雄哥算法星球的個人學(xué)習(xí)總結(jié)，B站英雄哥直播間：https://live.bilibili.com/24513717，每日凌晨5點(diǎn)到8點(diǎn)直播刷題。
注：本文章搬運(yùn)自個人博客。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

文章題目：【算法和數(shù)據(jù)結(jié)構(gòu)】前綴和-創(chuàng)新互聯(lián)
本文鏈接：http://www.chinadenli.net/article40/dcdgeo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站排名、自適應(yīng)網(wǎng)站、網(wǎng)站制作、微信小程序、定制開發(fā)、搜索引擎優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)