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, 2 days 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

»
2 days 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+2^k-1]$$$. x[0][i]=a[i] and for each $$$k\geq1$$$, x[k][i]=min(x[k-1][i],x[k-1][i+(1ll<<(k-1)]). The complexity is $$$O(n\log n)$$$, since $$$k\leq\log n$$$, $$$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 $$$2^y\leq 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
  • »
    »
    2 days 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
    • »
      »
      »
      2 days 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
      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        true

        → Reply
        • »
          »
          »
          »
          »
          38 hours ago, # ^ |
          ← Rev. 2   Vote: I like it -14 Vote: I do not like it

          false, $$$O(nq)$$$ is much simplier to understand and implement.

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

            O(qn)May lead to TLE

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              32 hours ago, # ^ |
                Vote: I like it -9 Vote: I do not like it

              It can't if you write cache-efficient code.

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

You can do it offline with ordered stack

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

This is dp ...

→ Reply