一、什么是前綴和
前綴和是一種預處理，用于降低查詢時的時間復雜度，
舉個例子：給定 n 個整數，然后進行 m 次詢問，每次詢問求一個區間內值的和，
如果用暴力寫法，那每次詢問都需要從區間左端點回圈到區間右端點求和，時間復雜度較大，
這種時候就可以預先求出該陣列的一維前綴和，
則 ans=s[R]-s[L-1] ，其中 L 和 R 是給定的區間，每次詢問可直接輸出答案，這樣時間復雜度就降到了 O(N+M)
二、前綴和的實作
1、一維前綴和: 用陣列preSum[i]表示nums的前i項和，i從1開始
preSum[ i ]=preSum[ i-1 ] + nums[ i ]
一般用于求區間[l,r]的值
ans = preSum[ r ] - preSum[ l-1 ]
2、二維前綴和: 用陣列S[i][j]表示前i項，前j項的總和, i , j 從1開始
preSum[ i ][ j ] = preSum[ i-1 ][ j ] + preSum[ i ][ j-1 ] + nums[ i ][ j ] - preSum[ i-1 ][ j-1 ]
用于求子矩陣 (x1,y1) (x2,y2)的值
ans = preSum[ x2 ][ y2 ] - preSum[ x2 ][ y1-1 ] - preSum[ x1-1 ][ y2 ] + preSum[ x1-1 ][ y1-1 ]
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/550086.html
標籤：C++
下一篇：java -- 執行緒(二)