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

$ curl repovive.com/roadmaps/dynamic-programming/prefix-sums/kuriyama-mirai-s-stones-implementation

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

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

$ curl repovive.com/roadmaps/dynamic-programming/prefix-sums/kuriyama-mirai-s-stones-implementation

Repovive

Codeforces 869B Kuriyama Mirai's Stones - Implementation - Prefix Sums | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

Codeforces 869B Kuriyama Mirai's Stones - Implementation

The code

Here's the full solution:

function solve(a, queries)
    n := length of a
    b := copy of a
    sort(b)
    // Build prefix sums for both arrays
    pref1 := array of size n + 1
    pref2 := array of size n + 1
    pref1[0] := 0
    pref2[0] := 0
    for i from 1 to n
        pref1[i] := pref1[i - 1] + a[i]
        pref2[i] := pref2[i - 1] + b[i]
    // Answer queries
    for each (type, l, r) in queries
        if type = 1 then
            print pref1[r] - pref1[l - 1]
        else
            print pref2[r] - pref2[l - 1]

Time: $O(n \log n + q)$ for sorting plus queries. Space: $O(n)$ .

The sorted array lets you pick the smallest elements in any range. Prefix sums on both arrays give $O(1)$ range queries.