• Basically an Array same length of the given array
  • The value at each index is the sum of values from index 0
  • Efficiently calculates sums of ranges within an array by leveraging on Memoization


O(1) Range Sum Query

  • With one time computation of the Prefix Sum (前缀和) in O(n), we can retrieve the sum of elements in a Contiguous Segment in O(1)
  • Let be a prefix sum of a given array, sums up the element in between the and (inclusive) of the given array
  • Thus, we can obtain the sum of any sub-sequence of the given array in O(1) with the following formula


is same as


Time Complexity

Practice Questions