res_and_ser's blog

Segment Trees and my every lasting problem
By res_and_ser, 6 years ago, In English

Hello all

Can anyone tell me how to solve this problem?

Query 1 — Equate all elements in range l to r equal to x

Query 2 — Find sum of all the elements from range l to r.

Constraints : n  <  =  100000

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

Comments Comments (8)
| Write comment?
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This is classic segment tree with lazy propagation problem, just use google or etc...

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

    Can you share the code?

    I am new to segment trees and I am finding it tough to code the update part.

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

      code

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

        Thanks for your code. :)

        It worked.

        By the way, can we do the same update thing using a fenwick tree?

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

          I think it's impossible to assign value on segment, using fenwick tree :(

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

Hi, you can learn a lot from here: Easy and efficient segment trees

Basically your query 1 is a interval modification using lazy propagation (calculating only the values you need when you need them) and the query 2 is a basic range query. Everything is explained in the link I provided. GL

→ Reply