Блог пользователя vis10326

segment tree
Автор vis10326, 10 лет назад, По-английски

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.

  • Проголосовать: нравится
  • -13
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        10 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +17 Проголосовать: не нравится

        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

        → Ответить
        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
          ← Rev. 7   Проголосовать: нравится +11 Проголосовать: не нравится

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

          Really higher :D

          → Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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://codeforces.me/problemset/problem/242/E and here is my code:http://codeforces.me/submissions/vis10326#.i will be greatly thankful to you

→ Ответить