Prefix Sum Concept & Pattern

🧠 Concept

• Sum of previous elements and itself for each slot

  • Extended to state of previous elements plus the current element (状态的叠加)

• Subarray/Range sum problems

  • Compute the sum of elements between two indices frequently

  • Find or count the number of subarrays that add upto a specific value

• 区间查询

🛠️ Pattern

• Dummy 0
• Help of hash table