Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

saptarshikuar2003's blog

Is it possible to locate the max or min value in a range of indices l,r in an array for q queries??
By saptarshikuar2003, history, 6 weeks ago, In English

lets say we have an array a of length n.

we are given q queries with indices l,r.

we have to locate the position of minimum or maximum value within that range....of l,r.

the constraints are
.........1<=n<=10^5 .........1<=l<=r<=n .........1<=ai<=10^9 .........1<=q<=10^5

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
6 weeks ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

You can do it by preparing a 2D array x where x[k][i] is the minimum/maximum value in range [i,i+2k−1]. x[0][i]=a[i] and for each k≥1, x[k][i]=min(x[k-1][i],x[k-1][i+(1ll<<(k-1)]). The complexity is O(nlogn), since k≤logn, i<n and each x[k][i] can be calculated in O(1) time.

Then, to calculate the minimum/maximum value of the range [l,r], calculate the largest number y such that 2y≤r−l+1. The answer is min(x[y][l],x[y][r-(1ll<<y)]).

To also find the index of that element, simply use this technique on an array of pairs b[n], where b[i]={a[i],i}.

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    at that point, just use segtree 

    struct node {
    int val, index; 
}

    everytime you merge two node, you merge val and index(updating val to min/max and index to new min/max)

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's what I'd do if I had to solve this, but I think what I described might be more simple. Although the way segment trees work is easier to understand, the implementation is a bit tricky, so I wouldn't recommend using a segment tree for this problem if it's the first time you use one.

      → Reply
»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

You can do it offline with ordered stack

→ Reply
»
6 weeks ago, # |
  Vote: I like it -25 Vote: I do not like it

This is dp ...

→ Reply