Abu-Gasem1's blog

Segment Tree
By Abu-Gasem1, history, 9 years ago, In English

Hey My Quesiotn Is About Segment Tree.

I Already Read The source code for it From Comptetive Prog 3 But What I need to know is how to Do The Lazy Updating Or The Lazy Teqh.

Can Any One Give And Example So I Can UnderStand This Teqh Im Facing A Proplem With UnderStanding This Teqh.

And Another Thing Im Wondring If I Can Solve This Proplem Using Segment Tree

The Link : (http://codeforces.com/contest/283/problem/A);

My Submission : (http://codeforces.com/contest/283/submission/12340325)

Sorry For My Boor English . Have A Nice Day.

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

»
9 years ago, # |
← Rev. 8   Vote: I like it 0 Vote: I do not like it
  • Firstly , my English is very poor ....
  • Because this problem is about interval modify , we had better use the lazy function.
  • let's create this struct
  • struct segtree {
  • int left , right; //the segtree's index's left and right
  • long long sum , flag; // the segtree's interval's sum and flag
  • }
  • the flag is about lazy
  • I just give you an example
  • if you update interval is [1,100] , and variable is x;
  • if you update all node , the time costs too much ,because you will update[1,1] , [2,2] ,...[100,100]
  • But we needn't do this work.
  • When we use this interval , we let the node's parent pass the flag to it.
  • ..Sorry , poor English , You can see my code for understanging better.
  • [Your text to link here...]
  • (http://codeforces.com/contest/283/submission/12350779)`
  • Actually , this problem has a better function, it solves more easier.
  • my god I really don't know how to post it look clear= =
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No Proplem I Will Try To UnderStand it From The Code Thanks Very Much

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

First my English is poor too...

Lazy Propagation: you don't need to update all of the elements in the segment,just update the parent when it's total overlap and mark it's children for later...

First: If you don't understand segment tree 100% watch this

segment tree:build,answer a query and normal update java code just under stand algorithm don't worry for it's programming language.

Lazy Propagation Article here

Easy and some hard problems Here

→ Reply