viesis's blog

Help with Segment Tree
By viesis, 9 years ago, In English

Hello all,

I have read segment tree, lazy propagation tutorials. but I find difficult to solve some problems like this one. Can anyone give more necessary tutorials or problems links to master segment tree?

Thanks in advance.

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

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

Algorithm Gym :: Everything About Segment Trees This is a very good tutorial. Enjoy it !!

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

That problem can be solved with a self-balancing BST in O(NlogN) or with a segment tree in O(Nlog2N) as far as I know.

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

    There is a O(NlogN) solution with segment tree.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You're right, I didn't give it much time. When you traverse the tree, you decide to go left or right depending on the number of elements on each interval, so it's NlogN effectively. I was actually thinking in the O(Nlog2N) solution using BIT when I said "segment tree".

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

    Hi, I had an idea, but I am terrible at implementation, so can you help ensuring if my approach will be correct? or Is there any valid similar approach?

    01. In the tree we will take a cnt variable where we will save how many items we have removed so far till the current position.
02. While removing an item from position pos we will increase the cnt value by 1 from pos to end position.
03. In the array we will always save value in their previous position(1 based index).
04. For example let the array is A[] = {2,3,4,5,6}
05. The cnt value in the tree is cnt[] = {0,0,0,0,0}
06. If the query is (c,2) cnt[2] = 0; So we will print A[2+0] which is 3.Update from (2+0) to End by increasyng cnt value by 1 and set A[2+0] = -1.
07. Now A[] = {2,-1,4,5,6} and cnt[] = {0,1,1,1,1}
08. If the query is (a,5) we add this to the end of array.
09. Now A[] = {2,-1,4,5,6,5} and cnt[] = {0,1,1,1,1,1}
10. If the query is (c,3) cnt[3] = 1; So we will print A[3+1] which is 5.Update from (3+1) to End by increasyng cnt value by 1 and set A[3+1] = -1.
11. Now A[] = {2,-1,4,-1,6,5} and cnt[] = {0,1,1,2,2,2}

    Thanks!

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

      If at the end of all your steps, you get a query (c,3), you have cnt[3] = 1, so you will print A[3+1] = -1, while the correct answer is to print A[5]. With BIT, you would need to do O(log2N) per query, though you can achieve O(logN) using segment tree by storing in each node the total number of people in that range.

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

I think it uses order statics. Each node of segment tree can store the number of active soldiers in the line.

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

fffuuuu!

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

https://www.hackerearth.com/notes/segment-tree-and-lazy-propagation/

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

You are legendary grossmeister, you must know everything about segment trees.

→ Reply