01 Prefix Sum - sum till n

1. Prefix Sum

Requirement - Any array
Core Problem - I need to get sum of all elements in my array between i till j position, again and again help me
Core Logic :

• if sum of a subarray is used frequently, store sum - till each element.
• Sum from position i till j is equal to = P[j] - P[i-1]

hashcomics

1 / 16

Steps:

1. Preprocess the array A to create a prefix sum array: P = [1, 3, 6, 10, 15, 21].
2. To find the sum between indices i and j, use the formula: P[j] - P[i-1].

Sample Problem:

Given an array nums, answer multiple queries about the sum of elements within a specific range [i, j].

Example:

• Input: nums = [1, 2, 3, 4, 5, 6], i = 1, j = 3
• Output: 9

LeetCode Problems:

1. Range Sum Query - Immutable (LeetCode #303)
2. Contiguous Array (LeetCode #525)
3. Subarray Sum Equals K (LeetCode #560)