Here's the full solution:
plaintext 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 Each (type, l, r) in queries if type = 1 print pref1[r] - pref1[l - 1] else print pref2[r] - pref2[l - 1]
Time: for sorting plus queries. Space: .
The sorted array lets you pick the smallest elements in any range. Prefix sums on both arrays give range queries.