3
$\begingroup$

I am given a $N$-length integer array. For each integer, I am given 4 values:

$$[\mathit{left},\mathit{right},t,\mathit{value}]$$ $$1\leq \mathit{left},\mathit{right},t\leq N$$

For each query, I have to find the sum of values which have $x$ in the range $[\mathit{left},\mathit{right}]$ and that satisfy $t\leq t_1$.

Example query: $x=5$, $t_1=4$.

So I have to find out sum of all the values satisfying $\mathit{left} \leq 5 \leq \mathit{right}$ and $t \leq 4$.

$\endgroup$
  • $\begingroup$ Without the $t_1$ requirement the problem can be solved using BIT or Segment Tree by doing sum of intervals and query on points in $O(log N)$. If you are allowed to solve queries offline you can sort queries by $t$ and follow previous idea, or use a persistent data structure. $\endgroup$ – Marcelo Fornet Oct 9 at 14:56
  • $\begingroup$ @MarceloFornet Suppose t1 requirement is not there, then how to solve this problem , can you elaborate? Yes, everything is offline here.. $\endgroup$ – Shalini Tomar Oct 9 at 14:59
1
$\begingroup$

When the value of $t_1$ is not present you are just given weighted intervals from left to right with weight value, and you should ask questions of the form, what is the sum of the weights of intervals that contains x.

If we know all intervals/weights before hand this whole task is easy without any fancy data structure, just adding the beginning of the interval with weight +value and the end with weight -value and accumulate all such values. The answer will be constant in intervals and to find the value at $x$ you can binary search for the interval that contains $x$. Will not go deep into this solution since it will not allow us to solve the problem when $t_1$ constraint is used again.

Assume we don't know all intervals before hand and we have a mix in of, add new interval, find sum of all intervals containing $x$. You can solve this problem using segment tree with lazy propagation to add a value on intervals fast, and query sum on points (actually with segment tree you can query in intervals but it isn't required here). Both queries are done in $O(log N)$ where $N$ is the number of intervals.

Let's call all given intervals in the input updates. To solve the problem with $t_1$ back, sort all queries and updates by $t$ value. And process them in such order. When you are processing each query of type $(x, t_1)$ only intervals with lower $t$ are present in the data structure, so we have an instance of the previous problem, ask for all intervals containing $x$, whenever you get an update, add it to the data structure.

This solution is offline, since you require to know all queries beforehand. This can be solved online using persistent segment trees. The overall complexity of the solution described here is $O((N+Q) log N)$.

$\endgroup$

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.