Shayan.P's blog

A data structure for maximizing and asking sum of a segment
By Shayan.P, history, 6 years ago, In English

Hello every one... I need a data structure handling two type of queries. 1. Maximize(l,r,x) 2. Sum(l,r)

I have a O(sqrt(n)*log(n)) solution using sqrt decomposition + set.But I am looking for a better solution. Thanks in advance

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Shayan.P (previous revision, new revision, compare).

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

Maximise (l,r,x) means set a[i] = max(a[i], x) ?

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

Segment tree beats.

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

    It was awesome. Thank you!

    Btw do you have any link to Chinese trick like this?

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

It's possible sqrt decomposition in this case without logarithmic factor? (Lazy sqrt decomposition or dsu approach? Yeah... segment tree beats is cool)

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

    By setting a proper bucket size, you can achieve per query.

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

      Yeah, I know...,but with potential function analyze (7'-'). u.u maybe, I hope :v

      → Reply