Prefix Sum

Keywords: prefix sum, range sum, range exist, range sum congruence modulo

前言

最近常常沒有寫出prefix sum變形的題目，這類型的題目設計上，往往都是實作簡單，但是沒想到就難以換其他方式完成。

下面舉一些比較經典，可以用prefix sum完成的變形題，注意這些題目都是在問subarray相關。

子陣列和整除數字K問題

其實就是同餘問題，問你有多少前綴跟目前數字對K取模下同餘

• Leetcode 974. Subarray Sums Divisible by K
• Leetcode 1590. Make Sum Divisible by P

子字串中，個別文字的奇偶數

其實根本也是同餘問題(mod 2)，同時記錄多個prefix xor sum，問是否每個字都出現偶數次，或最多只能有一個字出現奇數次等。

• Leetcode 1915. Number of Wonderful Substrings
• Leetcode 1542. Find Longest Awesome Substring
• Leetcode 1371. Find the Longest Substring Containing Vowels in Even Counts

子陣列和為指定數字

就是問有沒有曾經的prefix sum等於cursum - goal

• Leetcode 560. Subarray Sum Equals K
• Leetcode 930. Binary Subarrays With Sum

子陣列中是否「存在」某些數字

若可能出現的數字很少時，能透過prefix sum挑選個別數字是否有在某個區間出現

• Leetcode 1906. Minimum Absolute Difference Queries
• 跟上一題一樣，但數字範圍很寬，無法簡單對每個數字都記錄位置：https://codeforces.com/contest/765/problem/F