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