Codeforces 869B Kuriyama Mirai's Stones - Problem Statement

This is Kuriyama Mirai's Stones from Codeforces. You have an array of $n$ stones with weights. Queries come in two types: Type 1: Sum of stones from $l$ to $r$ in the original array. Type 2: Sum of stones from $l$ to $r$ if the array were sorted.

You need to answer both types quickly. Think about it: how many prefix arrays do you need? Build $2$ prefix arrays: one on the original, one on the sorted version.