Segment tree with n elements where n is not a power of 2

int sum(int a, int b) {
  a += n;
  b += n;
  int s = 0;
  while (a <= b) {
    if (a % 2 == 1) s += tree[a++];
    if (b % 2 == 0) s += tree[b--];
    a /= 2;
    b /= 2;
  }
  return s;
}

void add(int k, int x) {
  k += n;
  tree[k] += x;
  for (k /= 2; k >= 1; k /= 2) {
    tree[k] = tree[2 * k] + tree[2 * k + 1];
  }
}

I found this implementation of a segment tree in the book Guide to Competitive Programming. How would this handle any number of elements n where n is not a power of 2?

When n isn’t a power of two, you would round up n to the closest power of 2 greater than or equal to n.

For instance:

If n is 69, then the size of the tree would be 128.

What would you fill the remaining spots with in the tree?

n doesn’t have to be a power of two

see this cf blog:

1 Like

It depends on what type of segment tree you’re making. If you’re making a sum segment tree, then it would be zeros. If you’re making a min segment tree, then it would be filled with positive infinity.

Ok, thank you. How would I alter the current implementation to work for any number of elements?

Wdym by an number of elements?

Sorry, that was a typo. I meant any

Let’s say you’re given n.

The implementation for initializing the segment tree would be:

	int size; // Number of nodes in the segment tree
	vector<ll> segtree; // Stores the segment tree
	void init(int n){
		size = 1;
		while(size < n) size *= 2;
		sums.assign(2 * size, 0LL);
        // The size of the segment tree would be whatever 2 * size is.
	}