Questions tagged [range-query]
95 questions
13
votes
5 answers
How to increment all values in an array interval by a given amount
Suppose i have an array A of length L. I will be given n intervals(i,j) and i have to increment all values between A[i] and A[j].Which data structure would be most suitable for the given operations?
The intervals are known beforehand.
SHB
- 589
- 1
- 6
- 18
10
votes
3 answers
Range Queries in Cassandra (CQL 3.0)
One main part of Cassandra that I don't fully understand is its range queries. I know that Cassandra emphasizes distributed environment and focuses on performance, but probably because of that, it currently only support several types of ranges…
keelar
- 5,814
- 7
- 40
- 79
9
votes
3 answers
CSES Range Query Question: Salary Queries
I'm trying to solve this problem: https://cses.fi/problemset/task/1144/
Given an array of up to 200000 elements, my task is to process up to 200000 queries, which either ask me to update a single value within the array or ask me to find the number…
Christopher Miller
- 861
- 4
- 9
9
votes
4 answers
How to efficiently find a contiguous range of used/free slots from a Fenwick tree
Assume, that I am tracking the usage of slots in a Fenwick tree. As an example, lets consider tracking 32 slots, leading to a Fenwick tree layout as shown in the image below, where the numbers in the grid indicate the index in the underlying array…
Alex
- 13,024
- 33
- 62
6
votes
2 answers
How to implement range search in KD-Tree
I have built a d dimensional KD-Tree. I want to do range search on this tree. Wikipedia mentions range search in KD-Trees, but doesn't talk about implementation/algorithm in any way. Can someone please help me with this? If not for any arbitrary d,…
Ankit Kumar
- 1,145
- 9
- 30
6
votes
4 answers
How could I utilize algorithms for nearest neighbor search to do fixed radius search?
There are lots of works for the nearest neighbor search problem, so I wonder if I want to do fixed radius range search, could I utilize those algorithms for nearest neighbor search?
perhaps I could do kth-nearest-neighbor search over and over again…
Alaya
- 3,287
- 4
- 27
- 39
6
votes
1 answer
Doing range queries in Mongoose for Hour / Day / Month/ Year
Trying to figure out how to do this. Basically I want to sort by Hour / Day / Month / Year of my submissions.
Each submission has a created field which contains a Mongoose Date object in the form of "created" : ISODate("2013-03-11T01:49:09.421Z").…
bob_cobb
- 2,229
- 11
- 49
- 109
5
votes
4 answers
Find all subtrees in a BST whose keys lie in a given range
I was given this question during a recent interview: Given a BST whose nodes contains an Integer as value, find all subtrees whose nodes fall between integers X (min) and Y (max), where X
Quest Monger
- 8,252
- 11
- 37
- 43
5
votes
4 answers
MySQL: Forcing query to use indices with local variable in WHERE clause
Context
I have an application that selects a weighted random entry from a table for which prefix summation (of weights) is a crucial part. The simplified table definition looks like this:
CREATE TABLE entries (
id INT NOT NULL PRIMARY KEY…
concat
- 3,107
- 16
- 30
5
votes
2 answers
Finding the minimum element in a given range greater than a given number
We are given N (N <= 106) points on a 2D plane and an integer D (N <= 106), we want to find two points p1,p2 (p2 to the right of p1) such that the difference between p1.y and p2.y is at least D and p2.x - p1.x is minimized.
The x and y axis are in…
2147483647
- 1,177
- 3
- 13
- 33
4
votes
1 answer
How range and phrase query work in elasticsearch?
If elastic search is using inverted index, I want to know how elasticsearch is able to support range queries and phrase queries.
Note: I saw that inverted index supports them but i am not clear on how they do it internally.
Divya Paulraj
- 123
- 1
- 7
4
votes
2 answers
Range search in d-space with discrete coordinates
I would like to develop a range searching algorithm that reports all points within a given distance of a query point.
The points are specified by d integer coordinates in a tiny range, say up to 6 bits per dimension (range 0..63), for a total bit…
user1196549
4
votes
1 answer
Cassandra CQL range query rejected despite equality operator and secondary index
From the table schema below, I am trying to select all pH readings that are below 5.
I have followed these three pieces of advice:
Use ALLOW FILTERING
Include an equality comparison
Create a secondary index on the reading_value column.
Here is my…
naomi
- 1,934
- 1
- 14
- 29
3
votes
0 answers
Range max sum query using sparse table
I Implemented range max sum query using sparse Table ,I Know more efficient approach would be using segment trees.
What I have tried:
I am calculating the max sum in the range (i,2^j-1) for all possible value of i and j and storing them in a…
12341c0des
- 31
- 2
3
votes
2 answers
How is it possible to apply the lazy approach to update a segment tree if the update is more complex than simple addition or multiplication?
Consider this question. In this segment tree solution, we are updating all nodes of the tree in the given range. Is it possible to apply lazy propagation to this problem?
Edit: Consider that in every update operation arr[i] = (1-(1-arr[i])*a),…
yobro97
- 1,125
- 8
- 23