# 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.
}
``````