Range Query with conditions

Question

Suppose I have an $N$ length integer array of pairs of the type $[value, key]$. Now, I need to query for range sum. Query is of the type : $l, N, x$ meaning I have to sum up all the $value$ in the index range $l$ to $N$ having key as $x$. Also, there can be updates that add a new pair to the end of the array increasing $N$. Succeeding queries consider the updated $N$. There can be multiple queries so I need to answer the query in $O(logN)$ but precomputation is allowed.

I think it might be done with a Segment Tree but I cannot see what to keep in the nodes. Is it even possible to do it with required complexity, because I feel you actually need to go to every element in the array to check it's key. Any help is appreciated.

Answer 1

Since there are no updates there is a rather simple solution. Store a map of key -> array of pairs, such that for every element in your original vector (value, key) at position pos, you store in the vector associated with given key in the map the pair (position, value). Keep every vector sorted by position.

For example in the input array: $$[(3, 1), (2, 3), (2, 5), (1, 6), (3, 3)]$$ you would build the map:

{
    1 : {(4, 6)} // (value 6 at position 4)
    2 : {(2, 3), (3, 5)}
    3 : {(1, 1), (5, 3)}
}

Notice that with this data structure you can solve queries in vector by finding the sum in suffix. First find the corresponding vector in $O(log N)$ (possible in $O(1)$ if used unordered_map instead of map) and use lower_bound (also in $O(log N)$) to determine the target suffix. You should keep cumulative sums of the vector to calculate the sum on a suffix in $O(1)$.

---

To handle updates of the form add an element of the form (key, value) to the end of the original array you should only extend the vector corresponding with key in the map. You know the new position in the original array, which is greater than all previous position since it is at the end, so add the pair (new_size, value) to the end of the array associated with given key.

Notice that we must keep cumulative sum up to date, but cumulative sum up to the first $n$ values is equal to the cumulative sum up to the first $n-1$ values plus the last value. The new cumulative sum can be computed in $O(1)$.

Notice that in practice we don't need to have on each vector in the map a pair of (position, value), but instead (position, cumulative_sum).

Answer 2

Since you have specified that the array is unsorted, i am afraid you cant do a query in $O(logN)$, assuming we are talking about time complexity and not space complexity (but i think this is the case since you have expressed the desire to make the query efficient because there can be more than one). Keep in mind that (apart from a few exceptions which however do not help in ordering the type of array you have) the greater time complexity for sorting algorithms does not go under $O(n(logN))$, and that just for sorting the array.