vis10326's blog

segment tree
By vis10326, 10 years ago, In English

Why do we require a 4*n memory for each of the answer array and the flag array in segment tree with lazy propogation.Can not we work with 2*n memory for each of these arrays and also can not we do this thing that instead of using a flag in the parent node for indicating that it's children needs to be updated we set the flag in the children itself indicating that these needs to be updated.

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

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

Please can anyone explain why do we need 4*N memory for segment tree construction ?

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

    Actually we don't. It just makes the things easier.

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

    Actually we just need 2N - 1 nodes, where N >= n is a power of 2

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

      In the worst case it is 4*n if n = 2k + 1

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

        N ≥ n is a power of 2

        so your bound is actually higher (n = 2k + 1, N = 2k + 1, 2N - 1 = 2k + 2 - 1 = 4n - 5) :D

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 7   Vote: I like it +11 Vote: I do not like it

          n = 2k + 1 ------------ 4n = 2(k + 2) + 4 ------------ 2(k + 2) - 1 = 4n - 5

          Really higher :D

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

instead of using a flag in the parent node for indicating that it's children needs to be updated we set the flag in the children itself indicating that these needs to be updated

this is what i do. here is my code to solve HORRIBLE on SPOJ. if u dont understand it, u can post a comment here.

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

ok i have understood that but i have tried to solve a question by this method but it's giving runtime error. can you please help me in this? i am tired of fixing the bug but still not succeded here is the problem link :http://mirror.codeforces.com/problemset/problem/242/E and here is my code:http://mirror.codeforces.com/submissions/vis10326#.i will be greatly thankful to you

→ Reply