2024/11/06
序列 \(A_1, A_2,...,A_n\) 的長度為 \(i\) 的前綴和記為 \(S_i\) 而 \(S_0\) =0,可以用來計算區間和。
\(\sum\limits_{i = l}^r {A_i = S_r -S_{l-1}}\)
可以簡單理解為前 \(i\) 項的和,而求 \(l\sim r\) 的區間和自然就是\(S_r-S_{l-1}\)
多維前綴和的構造方式與一維相同,主要是求區間和時要利用容斥原理
如何構造 矩陣 sum?
\(sum_{r,c}=\sum\limits_{i = 1}^r \sum\limits_{j = 1}^c {arr_{i,j}}\)
遞推求 sum 的過程為(容斥原理):
\(sum_{i,j} = sum_{i-1,j} + sum_{i,j-1} - sum_{i-1,j-1} + arr_{i,j}\)
求子矩陣 (\(r_1 , c_1\))~(\(r_2 , c_2\)) 的和。
由遞推的算式可得 (\(r_1 , c_1\))~(\(r_2 , c_2\)) 的區間和為:
\(ans = sum_{r_2,c_2} - sum_{r_1-1,c_2} - sum_{r_2,c_1-1} + sum_{r_1-1,c_1-1}\)
圖例:
\(sum_{r_2,c_2} - sum_{r_1-1,c_2} - sum_{r_2,c_1-1} + sum_{r_1-1,c_1-1}\)
對一段長度為 \(n\) 的區間,做出 \(q\) 筆詢問
*詢問內容為區間和
每次詢問就遍例一次,直接暴力加法
for(int i=1;i<=q;i++){ int l,r,ans=0; cin>>l>>r; for(int j=l;j<=r;j++){ ans+=arr[j]; } cout<<ans<<"\n"; }
最差情況 : \(q\) 次詢問都是求 \(sum_{1,n}\)
因此你每次都需要遍例 \(1~n\),則時間複雜度為 \(O(q\cdot n)\)
開 \(10^2\cdot 10^2\) 的陣列,\(sum[i][j]\) 紀錄 \(i \sim j\) 的總和是多少
\(q\) 筆詢問即可 \(O(1)\) 解決掉 因此時間複雜度為 \(O(n^2+q)\)
開 \(10^6\) 的陣列, \(sum[i]\) 紀錄 \(i\) 的前綴和是多少
\(q\) 筆詢問即可 \(O(1)\) 解決掉 因此時間複雜度為 \(O(n + q)\)
int n,l,r,q; int arr[N]={},sum[N]={}; cin>>n; for(int i=1;i<=n;i++){ cin>>arr[i]; sum[i]=sum[i-1]+arr[i]; } cin>>q; for(int i=1;i<=q;i++){ cin>>l>>r; cout<<sum[r]-sum[l-1]<<"\n"; }
差分是一種和前綴和相對的策略,可以當做是求和的逆運算。
\(f_{i} = arr_{i} - arr_{i-1}\) , \(f_{1} = arr_{1}\)
ex: arr[] = 1 10 5 -3 9 f[] = 1 9 -5 -8 12
同時不難發現,\(arr_{i}\) 的值是 \(f_{i}\) 的前綴和
若要利用 \(f\) 計算 arr 的前綴和
\(sum_{1,n} = \sum\limits_{i = 1}^n \sum\limits_{j = 1}^i {f_j}=\sum\limits_{i = 1}^n (n-i+1)\cdot f_{i}\)
若要在 \(arr_l\) ~ \(arr_r\) 都加上 \(x\) 只需要修改 \(f_l\) 和 \(f_{r+1}\) 的值
f[l] += x; f[r+1] -= x;
對一段長度為 \(n\) 的區間,提出 \(k\) 次區間修改後詢問你一次結果
一樣直接暴力做,這邊就不贅述
int n,l,r,k,x; int arr[N]={},f[N]={}; cin>>n; for(int i=1;i<=n;i++){ cin>>arr[i]; f[i]=arr[i]-arr[i-1]; } cin>>k; for(int i=1;i<=k;i++){ cin>>l>>r>>x; f[r+1]-=x,f[l]+=x; }
前綴和是在非常多的題目都會用到的優化方式,也是一個簡單實用的技巧,請大家一定要時時刻刻想到前綴和。
另外 鑒於 xor 的性質(交換律),xor 也可以拿來進行前綴和。
而差分雖然不常用到,但卻是針對某些題目時好用的工具。
雙指針顧名思義,就是同時使用兩個指針,在序列、串列結構上指向的是位置,在樹、圖等資料結構結構中指向的是節點,通過邊或同向移動,或相向移動來維護、計算要求的資訊。
通過快指針以及慢指針(左指針和右指針)的移動去限制可選擇的區塊。
用 multiset 維護 sliding windows 內的數字
程式碼:
vector<int> ret; multiset<int> st; for(int i = 0; i < k; i++) { st.insert(nums[i]); } ret.push_back(*(st.rbegin())); for(int i = k; i < nums.size(); i++) { st.insert(nums[i]); st.erase(st.find(nums[i - k])); ret.push_back(*(st.rbegin())); } return ret;
也可以丟進 priority_queue 裡面(存 pair(value,index)),
每次查找最大值,檢查 index 是否是符合條件的,
若不符合就 pop 掉直到找到就好。
給一個長度為 \(n\)、由非負整數組成的陣列 \(a\),在 \(\sum\limits^r_{i = l}a_i \le S\) 的情況下,最大化 \(r - l\)。
雙指針維護左界跟右界,被左界跟右界框起來的區域就是我們想要的,但是左界跟右界要怎麼移動呢?
每次將右界向右移動一格,並當總和超過 \(S\) 時,將左界也向右移動。
\(S = 20\),初始化時,沒有包含任何區間。
\(l = 1, r = 1, sum \le 20, r++\)
\(l = 1, r = 2, sum \le 20, r++\)
\(l = 1, r = 3, sum \le 20, r++\)
\(l = 1, r = 4, sum \le 20, r++\)
\(l = 1, r = 5, sum > 20, l++\)
\(l = 2, r = 5, sum \le 20, r++\)
\(l = 2, r = 6, sum > 20, l++\)
\(l = 3, r = 6, sum > 20, l++\)
\(l = 4, r = 6, sum \le 20, r++\)
\(l = 4, r = 7, sum > 20, l++\)
\(l = 5, r = 7, sum > 20, l++\)
結束了
\(l\) 和 \(r\) 最多只會移動 \(n\) 步,複雜度 \(O(n)\)
程式碼:
for(int i = 0; i < n; i++) { sum += arr[i]; while(sum > s) { sum -= arr[l]; l++; } ans = max(ans, i - l + 1); }
給一個長度為 \(n\)、由非負整數組成的陣列 \(a\)
有幾組 pair \((l、r)\),符合 \(\sum\limits^r_{i = l}a_i \le S\)
再觀察一下上一題
對 \(r = 4\) 來說, \(l = 1, 2, 3, 4\) 都符合 \(\sum\limits^r_{i = l}a_i \le S\)
因此本題就是在上一題的基礎上,對每個右界計算有幾個左界可以符合條件。
程式碼:
for(int i = 0; i < n; i++) { sum += arr[i]; while(sum > s) { sum -= arr[l]; l++; } ans += (i - l + 1); }
遇到一個問題時,如果他是要求最好的區間或者是有幾個區間符合條件時,就可以考慮雙指針,至於指針要放哪,就要看題目而定了。
給一個為 \(n\) 的陣列 \(arr\)
\(a_i\) 代表在 \(x = i\) 的位置有高度為 \(a_i\) 的垂直線,
選兩個位置 \(i、j\) 且 \(i < j\),計算 \(\text{min}(a_i, a_j)\times (j - i)\) 的最大值
一開始先將指針放在最左邊跟最右邊,並比較兩邊的值,將值較小的指針往中間移,因為對這個指針來說,另外一邊的指針移動對答案是沒有貢獻的
int maxa = 0; int l = 0, r = n - 1; while(l < r) { maxa = max(maxa, (r - l) * min(arr[l], arr[r])); if(arr[l] < arr[r]) { l++; } else r--; }