This is Kuriyama Mirai's Stones from Codeforces. You have an array of stones with weights. Queries come in two types: Type 1: Sum of stones from to in the original array. Type 2: Sum of stones from to if the array were sorted.
You need to answer both types quickly. Think about it: how many prefix arrays do you need? Read the problem statement carefully, noting the constraints. Try to identify the recursive structure before looking at the solution.