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

segment tree space complexity
Автор arjun95, история, 8 лет назад, По-английски

how to prove space complexity in segment tree is O(4*n).

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

»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

Segment tree with 2^x leaf nodes will have 2^(x+1) — 1 total nodes because it is a perfect binary tree.

Now, you will have useless leaf nodes if you are using general n. Therefore at worst you will have almost 2*n leaf nodes because you must round up to the next power of two. If n is 2^j + 1, then you must have 2^(j+1) leaf nodes = O(2*n).

And as we proved before total nodes is ~2 * leaf nodes so we have 2*2*n = O(4n) total space.

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

    thanks for explanation. is there any other mathematical proof to prove this?

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

      If you're not satisfied by the above proof here is another:

      Last layer: nodes
      Pre-last layer: nodes


      So, we have nodes.
      You can see the infinite geometric progression on the right. Its sum is equal to , where is first element of progression ( here) and is ratio between two adjacent elements ( here).
      So, there is a total of nodes in a segment tree.

      → Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится -13 Проголосовать: не нравится

This problem was one of the INOI 2012-2013 problems.

At first note that we need exactly 2·n - 1 nodes, but if we use arrays and set id of left child of node with id Id to 2·Id and 2·Id + 1 id to right one, we need an array with size 4·n, let's prove.

Let f(n) the maximum id that we need in segment tree. Let's prove f(2n + 1) = 4·2n - 1. We can prove it using induction, f(21 + 1) = 7, f(2n + 1) = 2·f(2n - 1 + 1) + 1 = 2·(4·2n - 1 - 1) + 1 = 4·2n - 1.

Edit: Definition of f(n) has changed.

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

Let k be the smallest natural number such that 2k ≥ n. Note that 2k < 2 × n. We will find the answer for 2k. The segment tree, and indeed any other binary tree formed will have exactly k + 1 levels, the i-th containing 2i nodes. Then, the total number of nodes will be a geometric progression of the form 20 + 21 + 22 + ... + 2k, which is precisely equal to 2k + 1 - 1. Since 2k < 2 * n, it follows immediately that 2k + 1 - 1 < 4 × n, so the number of nodes of the new tree — greater than our answer — is still less than 4 × n.

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

Non-recursive segment trees use exactly 2n - 1 nodes.

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

    @AI.Cash: I've read u non-recursive segment tree. It's very easy, powerful as general segment-tree and required less memory space. But, in non-recursive segment tree how to find lower bound of position for given sum ?? // for perfect binary tree (i.e. n = 2^k):

       int find(int sum){
     int result = 1; 
     while(result < n){ 
          result <<= 1; 
          if(tree[result]< sum)sum-=tree[result++]; } 
     }
     return result;
}

    when n = 2^k, this works fine, but n != 2^k not.

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

      Indeed, for n ≠ 2k we basically get not one tree but O(logn) separate perfect trees. So, it doesn't support the techniques where we need to start from the root and move to the leaves, like binary search and fractional cascading.

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

        Thx. I'll use O(4n) case with your implementation in this case.

        → Ответить