0
$\begingroup$

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.

|cite|improve this question
$\endgroup$
  • $\begingroup$ is your array sorted in some way or are the values of $value$ and $key$ unsorted? $\endgroup$ – Yamar69 Oct 8 '19 at 13:11
  • $\begingroup$ @Yamar69 Sorry forgot to mention an important part about the query. And No, not sorted, the data is arbitrary. $\endgroup$ – resound Oct 8 '19 at 13:14
  • $\begingroup$ Do you need to solve each query online, or you can sort the queries before start answering them? In case you can sort them you can solve each of them in $O(log N)$, otherwise you can solve them in $O(log^2 N)$ using persistent segment trees. $\endgroup$ – Marcelo Fornet Oct 8 '19 at 13:42
  • $\begingroup$ You can also use wavelet trees. $\endgroup$ – Marcelo Fornet Oct 8 '19 at 13:44
  • $\begingroup$ @MarceloFornet That seems interesting. I have an update that adds a new pair at the end of the array, hence increasing $N$. The query also uses the updated $N$ (that is if there was an update that increased $N$, then succeeding queries use updated $N$). I actually thought about persistent segment trees but as I said, couldn't really implement it. $\endgroup$ – resound Oct 8 '19 at 13:47
1
$\begingroup$

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).

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Would be helpful if you can elaborate on the updates. :) Also, can you keep it a little c++ friendly (with the terms and containers) $\endgroup$ – resound Oct 8 '19 at 14:09
  • $\begingroup$ Sure I'll do it now, to keep the answer consistent with the question, consider adding the explanation of the update to the question. $\endgroup$ – Marcelo Fornet Oct 8 '19 at 14:11
  • $\begingroup$ Sure, added to the OP ! $\endgroup$ – resound Oct 8 '19 at 14:16
  • $\begingroup$ @Marcelo Fornet OP question was if it was possible to do it in $O(logN)$ time. The answer is that it cannot. The construction of your dictionary take the same time as sorting. to that you need to add the sums. $\endgroup$ – Yamar69 Oct 8 '19 at 14:17
  • $\begingroup$ @Yamar69 it is indeed possible to handle each query in $O(log N)$ $\endgroup$ – Marcelo Fornet Oct 8 '19 at 14:20
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Seems you're right. This is an unnecessary question. $\endgroup$ – resound Oct 8 '19 at 13:38
  • $\begingroup$ There is no need to sort the array to solve the problem. $\endgroup$ – Marcelo Fornet Oct 8 '19 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.