Subarray queries

You can decompose it the other way around. Namely, build a tree of half-arrays (this is (n log n) space). Sort each subarray and build a cumulative sum array for it. Now your queries are (log² n) each (log n to identify the subarrays and another log n to find the cumulative sum in each subarray).

For example, if your original array is

            5,10,2,7,16,4,8,9

you first build this tree

            5,10,2,7,16,4,8,9
              /         \
      5,10,2,7           16,4,8,9
      /      \           /      \
    5,10     2,7      16,4      8,9
    / \      / \      / \       / \
   5   10   2   7   16   4     8   9

then sort them all

           2,4,5,7,8,9,10,16
              /         \
      2,5,7,10           4,8,9,16
      /      \           /      \
    5,10     2,7      4,16      8,9
    / \      / \      / \       / \
   5   10   2   7   16   4     8   9

Now if you want to answer query say (1,6,8) (indices are 0-based) you decompose the (1,6) interval into binary subintervals (1) (2,3) (4,5) (6) (there's no more than 2 log n of those) then find the answer for each one separately (0 for (1)={10}, 9 for (2,3)={2,7}, 4 for (4,5)={16,4}, 8 for (6)={8}) and sum them up.

Initial tree building can be done in (n log n) if you sort pairs (value, index) once and then just pass over the sorted array log n times (once for each tree level) and copy the values to their respective nodes.