Prefix Sum Function
Programming Interview
Medium
4 views
Problem Description
Consider {x}. Write function build_prefix(arr) and answer sums fast.
Input Format
First line n q. Second line n integers. Next q lines l r.
Output Format
q lines sums.
Sample Test Case
Input:
5 3
1 2 3 4 5
1 3
2 4
4 5
Official Solution
import sys
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
it=iter(p)
n=int(next(it)); q=int(next(it))
a=[int(next(it)) for _ in range(n)]
def build_prefix(arr):
pref=[0]*(len(arr)+1)
s=0
for i,v in enumerate(arr, start=1):
s+=v
pref[i]=s
return pref
pref=build_prefix(a)
out=[]
for _ in range(q):
l=int(next(it)); r=int(next(it))
out.append(str(pref[r]-pref[l-1]))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!