2n memory segment tree by choosing midpoint

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Hi Codeforces! If you calculate midpoint like

int get_midpoint(int l, int r) {//[l, r)
	int pow_2 = 1 << __lg(r-l);//bit_floor(unsigned(r-l));
	return min(l + pow_2, r - pow_2/2);
}

then your segment tree requires only $$$2 \times n$$$ memory.

test

#include <bits/stdc++.h>
using namespace std;


int get_midpoint(int l, int r) {//[l, r)
	int pow_2 = 1 << __lg(r-l);//bit_floor(unsigned(r-l));
	return min(l + pow_2, r - pow_2/2);
}


int n;
set<int> internal_nodes, leaf_nodes;
map<int, int> depth_of_segments_not_pow2;

void build(int v, int l, int r) {//[l, r)
	if(r-l == 1) {
		const int depth_leaf = __lg(v), max_depth = __lg(2*n-1);
		if(l == 0) {//left-most leaf
			assert(v == int(bit_ceil(unsigned(n))));
			assert(depth_leaf == max_depth);
		}
		assert(depth_leaf == max_depth || depth_leaf == max_depth - 1);
		if((n&(n-1)) == 0) assert(depth_leaf == max_depth);
		assert(n <= v && v < 2*n);
		assert(!leaf_nodes.count(v));
		leaf_nodes.insert(v);
		return;
	}
	if(((r-l)&(r-l-1)) == 0) assert(get_midpoint(l,r) == (l+r)/2);
	else depth_of_segments_not_pow2[__lg(v)]++;
	assert(1 <= v && v < n);
	assert(!internal_nodes.count(v));
	internal_nodes.insert(v);

	int m = get_midpoint(l, r);
	build(2*v, l, m);
	build(2*v+1, m, r);
}

int main() {
	for(n = 1; n <= 520; n++) {
		cout << "n: " << n << endl;
		internal_nodes.clear();
		leaf_nodes.clear();
		depth_of_segments_not_pow2.clear();

		build(1, 0, n);

		assert(ssize(internal_nodes) == n-1);
		assert(ssize(leaf_nodes) == n);
		for(int i = 1; i < n; i++) assert(internal_nodes.count(i));
		for(int i = n; i < 2*n; i++) assert(leaf_nodes.count(i));
		//at most one "bad" segment per depth
		//either left child or right child (or both) will have segment length
		//a power of 2; then their subtrees are a perfect binary tree
		for(auto [depth, cnt] : depth_of_segments_not_pow2) assert(cnt == 1);
		assert(ssize(depth_of_segments_not_pow2) <= __lg(n));
	}
	return 0;
}

proof

induction assumption: the segment tree with root segment $$$[0,n)$$$ turns into a complete binary tree which has $$$2 \times n - 1$$$ nodes and max depth = __lg(2*n-1).

notes about induction assumption

observe:

0 = __lg(1)
1 = __lg(2) = __lg(3)
2 = __lg(4) = __lg(5) = __lg(6) = __lg(7)
...

so __lg(v) = depth of node v
max depth of complete binary tree = depth of any node on lowest level
node 2*n-1 is always on the lowest level

Also note: get_midpoint(l + x, r + x) = get_midpoint(l, r) + x so we can "shift" any segment $$$[l,r)$$$ to $$$[0,r-l)$$$ and the corresponding segment trees have the same structure, hint: min(a + x, b + x) = min(a, b) + x

Induction step

case 0: $$$r-l$$$ is a power of 2

details

case 1: $$$l + pow2 < r - \frac{pow2}{2}$$$

details

From this, the left and right childs have the same max depth; the left child is a perfect binary tree; the right child is a complete binary tree, so overall it's a complete binary tree.

case 2: $$$l + pow2 \ge r - \frac{pow2}{2}$$$

details

From this, the left child has max depth = 1 + right child max depth. The left child is a complete binary tree; the right child is a perfect binary tree, so overall, it's a complete binary tree.

I was inspired by ecnerwala's in_order_layout https://github.com/ecnerwala/cp-book/blob/master/src/seg_tree.hpp

I'll be waiting for some comment "It's well known in china since 2007" 😂

History