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