Questions tagged [range-query]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7 votes
2 answers
346 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 ...
bihariforces's user avatar
0 votes
0 answers
62 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 ...
Andrey Godyaev's user avatar
1 vote
2 answers
127 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 ...
chrylis -cautiouslyoptimistic-'s user avatar
0 votes
0 answers
29 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 ...
Avv's user avatar
  • 505
3 votes
1 answer
6k 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 ...
matheuscscp's user avatar