The trick: build two prefix sum arrays.
from the original array (for Type 1 queries)
from the sorted array (for Type 2 queries)
Sort a copy of the array once at the start. Build prefix sums for both versions. Each query checks its type, then uses the corresponding prefix array. Time:
Time complexity: for sorting, for building both prefix arrays, per query. Total: .
Space complexity: , for building both prefix arrays, per query. Total: .