Number of nodes in segment tree

Question

I'm just wondering how many nodes can be in segment tree. I know there is formula for it and it is: 2n-1. But for example if we have 5 data in a segment tree will there be 9 nodes in the tree or 15? So following that example whether the total number of members of the segment tree is equal to the binary sequence or not?

Answer 1

Technically, you can always create a segment tree using only 2n-1 nodes, but this is complicated to code, which is why we often increase the size of the array to the lowest power of 2 that is higher or equal to n.
The reason we do that is because in a perfect binary tree the parent of node i is i/2 and its sons are 2*i and 2*i+1. This makes an iterative approach very simple to code.
So in that tree, you will indeed have 2n-1 nodes, with n being the size of the extended array.
But this size is always <= 2*n so this doesn't affect asymptotic behaviour.

Note that in certain recursive implementations with struct pointers, you can limit the number of nodes to 2*n-1, but i wouldn't recommend implementing like this for simple trees.

Here is an example of the iterative approach i was talking about, here the segment tree is constructed to query sum of ranges in an array.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct SEG {
    ll sz;
    vector<ll> a;
    SEG(vector<ll>& input, int n) {
        for (sz = 1; sz<n; sz*=2);
        a.resize(2*sz);
        for (int i = 0; i<n; i++) a[i+sz] = input[i];
        for (int i = sz-1; i ; i--) a[i] = a[2*i]+a[2*i+1];
    }
    
    void update(int i, int x) {
        a[i+=sz] = x;
        for (i/=2; i; i/=2) a[i] = a[2*i]+a[2*i+1];
    }
    ll query(int l, int r) {
        ll res = 0;
        for (l+=sz, r+=sz; l<=r; l/=2, r/=2) {
            if (l%2==1) res+=a[l++];
            if (r%2==0) res+=a[r--];
        }
        return res;
    }
};