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

Array Size Needed for Segment Tree
Автор maxorand, 7 лет назад, По-английски

If the given array's size is N then what should I declare the size of the array for Segment Tree?

If I set the Segment Tree's array size to 2 × 2k (or maybe something like this 2 × 2k + 5) where k = ⌈ log2N⌉, won't that be enough? If not, then why?

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

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

2*N is enough.

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

    No, 2 * N will not hold for any N that is not a power of 2.

    For example if N = 105 then you will need roughly 262143 sized segment tree, which is greater than 2 * N. Actually 4 * N is the safest way.

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

Actually if you can write N as 2x where x is an integer then you can see that you need 2x + 1 - 1 nodes in your segment tree. So what can you do for other N's? Well, you can find the next power of 2 after N, let's say it is 2x and then you can declare 2x + 1 - 1 sized segment tree. So yes it will work as you said.

But if you don't want to do that much calculation, you can always declare 4 * N with your eyes closed!

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

Here is a nice Quora answer which proves that 4 is in fact the smallest k such that kN is enough space for a segment tree on an array of size N.

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

    But iterative segment tree takes only 2N space. 

    const int N = 100005;

int n, a[N], t[N + N];

void init() {
  for (int i = 0; i < n; ++i) {
    t[n + i] = a[i];
  }
  for (int i = n - 1; i; --i) {
    t[i] = t[i << 1] + t[i << 1 | 1];
  }
}

    See more here.

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

      Sure, the page I linked to assumes the recursive implementation, so the result it proves is not valid for the iterative implementation you suggest.

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

I usually adopt the implementation of segment tree mentioned in this book Competitive Programmer's Handbook — a new book on competitive programming.

According to my own understanding, if there are N elements, then I will find the minimum M = 2m that is no less than N. Then, the total number of nodes in the segment tree should be 2 * M.

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

You should change a little bit k=(int)log2(N)+1; Rest of them are ok .

→ Ответить