Questions tagged [range-query]
The range-query tag has no summary.
10 questions
2 votes
0 answers
51 views
Find all non-extendable ranges in an array of real values with a non-positive sum
I have a long array of size $n>10^6$, call it $X$. I would like to find all ranges $[a, b)$ satisfying the following conditions $\sum_{i=a}^{b-1}X[i] \leq 0$, $b-a \geq K$, $\sum_{i=a-1}^{b-1} X[i]...
- 21
2 votes
1 answer
51 views
Existence of inversion in range
Given segment $\left[L, R\right]$ check if there is an inversion in the segment. If $a_i > a_j$ and $j> i$ then it is an inversion. Can this done faster than a linear check given that we can ...
- 21
1 vote
1 answer
73 views
Efficient merging of overlapping ranges with values preserving sum
Given a list of ranges each with an associated value, the metric at a point is the sum of the values of all overlapping ranges. The goal is to produce a list of non-overlapping ranges that preserve ...
- 11
0 votes
1 answer
104 views
1 vote
1 answer
102 views
A data structure for range minimum queries
Here is a data structure question in the comparison model that I can't answer. I have an array $A$ of $n$ elements. I work in the comparison model, meaning that the elements can only be compared with ...
- 11
7 votes
2 answers
502 views
Queries to count points lying on arbitrary line
Suppose we have $N$ points on $XY$ plane, ie. $(x, y)$ and $x, y \in Z$ and multiple queries where each query is of the form $y = mx + c$ and $m, c \in Z$. Is it possible to count number of points ...
- 333
0 votes
0 answers
98 views
Zero sequence query in boolean array
I have a large array of bits of length $N$. The query $f(k, m)$ means "find $kth$ zero in the array and the next $m-1$ zeros after it", $k \in [0, N-1], m \ll N$ Currently I use a segment ...
- 297
1 vote
2 answers
206 views
Is there a data structure for lazy-loading time-series data?
I am writing a UI that needs to display a chat log, similar to Slack and Discord. In addition to being able to scroll and lazy-fetch additional pages in either direction, I need to be able to jump to ...
0 votes
0 answers
59 views
Sparse Table Memory Space Complexity
If we have input of size $N=13$, which represents array that has 13 element. We need in general $O(N\log{N})$ memory to store all intervals. We see that number of intervals we need in terms of power ...
- 553
4 votes
1 answer
7k views
Segment trees with insertion/deletion
I have a range-query problem to solve. This problem requires not only range queries and update, but also insert or delete an element of the array. There is a series of operations that must be done in ...
- 345