Teaching Kids Programming: Videos on Data Structures and Algorithms
Given an array of numbers, if we want to find out the sum of the interval, we can do this using a O(N) Loop. If there are M queries, then the time complexity is O(N^2). Could we do better? Yes, we can pre-compute the prefix sum using O(N) time and O(N) space. And with the prefix sum array, we can compute the sum of the intervals in O(1) constant time:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class PrefixSum: def __init__(self, nums): self.nums = nums self.computePrefixSum() def computePrefixSum(self): s = 0 self.prefixSum = [0] for i in self.nums: s += i self.prefixSum.append(s) def sum(self, frm, to): return self.prefixSum[to + 1] - self.prefixSum[frm] arr = PrefixSum([1,2,3,4,5,6,7]) print(arr.sum(2,5)) # print 18 print(arr.sum(0,1)) # print 3 print(arr.sum(3,6)) # print 22 |
class PrefixSum:
def __init__(self, nums):
self.nums = nums
self.computePrefixSum()
def computePrefixSum(self):
s = 0
self.prefixSum = [0]
for i in self.nums:
s += i
self.prefixSum.append(s)
def sum(self, frm, to):
return self.prefixSum[to + 1] - self.prefixSum[frm]
arr = PrefixSum([1,2,3,4,5,6,7])
print(arr.sum(2,5)) # print 18
print(arr.sum(0,1)) # print 3
print(arr.sum(3,6)) # print 22We push a dummy zero at the begining of the prefix sum array so that we don’t need to deal with the edge case when the “from” is the begining.
Range Query via Prefix Sum:
- Teaching Kids Programming – Prefix Sum Algorithm to Compute the Interval Sums
- C++ Range Sum Query – Immutable
- GoLang: Range Sum Query on Immutable Array via Prefix Sum
–EOF (The Ultimate Computing & Technology Blog)
GD Star Rating
loading...
375 wordsloading...
Last Post: Complete an Arithmetic Sequence by Finding Missing Number
Next Post: Depth First Search Algorithm to Compute the Sum of Nodes with Even Grandparent Values
