Stack Overflow
Stack Overflow

Questions tagged [rmq]

Given an array A[1,n] of n objects taken from a well-ordered set (such as numbers), a Range Minimum Query (or RMQ) from i to j asks for the position of a minimum element in the sub-array A[i,j].

Given an array A[1,n] of n objects taken from a well-ordered set (such as numbers), a Range Minimum Query (or RMQ) from i to j asks for the position of a minimum element in the sub-array A[i,j].

More info: Wikipedia

67 questions
25
votes
5 answers

How to use UIButton as Toggle Button?

I am trying to create a toggle button for each cell in my table. When pressed, it will change the image and when pressed again it will change the image again -- Toggle. In the UIButton class I don't see a selected state. I'm looking for a way to…
Anthony
  • 33,838
  • 42
  • 169
  • 278
23
votes
2 answers

How to adapt Fenwick tree to answer range minimum queries

Fenwick tree is a data-structure that gives an efficient way to answer to main queries: add an element to a particular index of an array update(index, value) find sum of elements from 1 to N find(n) both operations are done in O(log(n)) time and I…
Salvador Dali
  • 214,103
  • 147
  • 703
  • 753
22
votes
6 answers

What data structure using O(n) storage with O(log n) query time should I use for Range Minimum Queries?

I'm stumped by the following homework question for an algorithms class: Suppose that we are given a sequence of n values x1, x2 ... xn, and seek to quickly answer repeated queries of the form: given i and j, find the smallest value in xi...…
Channel72
  • 233
  • 2
  • 5
19
votes
3 answers

Solving Range Minimum Queries using Binary Indexed Trees (Fenwick Trees)

Formally, the Range Minimum Query Problem is: Given an array A[0, N-1] , Find the position of the element with the minimum value between any two given indices. Now, the standard solution is to use a segment tree and has been described here.…
Ankesh Anand
  • 1,695
  • 2
  • 16
  • 24
10
votes
1 answer

Range Minimum Query approach (from tree to restricted RMQ)

So, I read this TopCoder tutorial on RMQ (Range Minimum Query), and I got a big question. On the section where he introduced the approach, what I can understand until now is this: (The whole approach actually uses methodology introduced in Sparse…
Shane Hsu
  • 7,937
  • 6
  • 39
  • 63
8
votes
4 answers

Channel closed by server: 406 (PRECONDITION-FAILED) with message "PRECONDITION_FAILED - inequivalent arg 'x-max-priority' for queue 'xyz'

While running the app in consumer mode, my application is frequently crashing with an error Error: Channel closed by server: 406 (PRECONDITION-FAILED) with message "PRECONDITION_FAILED - inequivalent arg 'x-max-priority' for queue 'xyz' in vhost…
kavigun
  • 2,219
  • 2
  • 14
  • 33
7
votes
1 answer

Range Minimum Query approach (Last steps)

Continued from my last question "Range Minimum Query approach (from tree to restricted RMQ)" (It's recommended to give it a read) Again, from this tutorial on TopCoder, I have a few questions here and there, and I hope someone can clear them…
Shane Hsu
  • 7,937
  • 6
  • 39
  • 63
5
votes
1 answer

Count the number of ranges [L; R] which has difference between the maximum and minimum is even

Given an array n elements (n <= 10^5) Count the number of ranges [L; R] (L <= R) which has difference between the maximum and minimum is even. For example, n = 5 a[] = {4, 5, 2, 6, 3} The answer is 11: [1;1], [1;4], [1;5], [2;2], [2;4], [2;5],…
Hiển Nguyễn Minh
  • 303
  • 1
  • 9
4
votes
1 answer

Range Minimum Query approach (Query)

Continued from my last two questions, "Range Minimum Query approach (from tree to restricted RMQ)" and "Range Minimum Query approach (Last steps)" I followed this tutorial on TopCoder, and the approach is introduced in the last section. Now…
Shane Hsu
  • 7,937
  • 6
  • 39
  • 63
2
votes
1 answer

Spring RabbitMQ PooledChannelConnectionFactory, transactional vs non-transaction pool settings

I have a Spring Boot service that needs to listen to messages across multiple RMQ vhosts. So far I only need to consume messages, though in the short future I might need to publish messages to a third vhost. For this reason I've moved towards…
user731842
  • 202
  • 2
  • 6
2
votes
0 answers

Segment tree lazy propagation max query when update is non uniform

I am facing a problem in lazy propagation of segment tree. I have an array A, of length N ,of smaller arrays (of max length 20). I also have an array of indices B, referring to the index i am currently pointing to in the array Ai. There are 2…
Rajarshi basu
  • 330
  • 1
  • 10
2
votes
1 answer

Range minimum queries when array is dynamic

I have an array say A(0 indexed) of size 1. I want to find minimum in array A between indexes k1 (k1>=0) and A.size()-1(i.e the last element). Then I would insert the value : (minimum element in given range + some "random" constant) at the end of…
Naman Agarwal
  • 151
  • 7
2
votes
1 answer

Simplest way to set a background image on a ProMotion screen?

I just want to set a background image on a screen for a placeholder. What is the quickest, easiest, simplest way to do that? Everything I've tried does not seem to work. I should mention that this is in RedPotion so I already have access to RMQ.
Andrew
  • 227,796
  • 193
  • 515
  • 708
2
votes
3 answers

Efficiently convert array to cartesian tree

I know how to convert an array to a cartesian tree in O(n) time http://en.wikipedia.org/wiki/Cartesian_tree#Efficient_construction and http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#From RMQ to LCA However, the…
dhruvbird
  • 6,061
  • 6
  • 34
  • 39
2
votes
4 answers

Multiplication in a range

I have an array to 10 numbers supprse A[10] = {1,2,3,4,5,6,7,8,9,10} and I have to compute the multiplication of numbers in a particular range but not getting correct answer, I am using segment tree and dont know how to use query operation Here is…
avinashse
  • 1,440
  • 4
  • 30
  • 55
1
2 3 4 5