#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/prefix-sums/prefix-sums-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/prefix-sums/prefix-sums-implementation

Repovive

Prefix Sums - Implementation - Prefix Sums | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units

Open in Course

Prefix Sums - Implementation

The code

function buildPrefix(a, n)
    pref[0] := 0
    for i from 1 to n
        pref[i] := pref[i-1] + a[i]
    return pref

function rangeSum(pref, l, r)
    return pref[r] - pref[l-1]

Watch the indexing. If your array is $0$ -indexed, adjust the formula to $pref[r+1] - pref[l]$ . Off-by-one errors are the most common bug here. Trace through a small example by hand before submitting.

Time complexity: $O(n)$ to build, $O(1)$ per query.

Space complexity: $O(n)$ for the prefix array.

HannahHi! I'm Hannah. Let me know if you need help understanding anything!