An extension of the blog Efficient and easy segment trees.

Single element modification + find nearest previous element smaller than value

For recursive implementation, see this comment: https://codeforces.me/blog/entry/55083#comment-389949.

Non-recursive implementation: First it's necessary to find any parent of the target node. There are two methods.

• Method 1 (similar to the query range function): divide the range [0..x+1[ into $$$\log n$$$ ranges, find the rightmost range with minimum value smaller than val.
• Method 2: just traverse the tree to the left starting from node x. For simplicity, assume the last element of the array is $$$-\infty$$$. (only required in method 2)

(t[x] is the minimum value in node x.)

#define METHOD_1 /* 1 or 0 */
int previous_less_than(int x, int val) {
	x += n;

#if METHOD_1
	int found_node = -1;
	for (int l = n, r = n + x + 1; l < r; l >>= 1, r >>= 1) {
		if (l & 1) {
			if (t[l] < val) found_node = l;
			++l;
		}
		if (r & 1) {
			--r;
			if (t[r] < val) {
				found_node = r;
				break;
			}
		}
	}
	if (found_node < 0) return -1;
	x = found_node;
#else
	while (t[x] >= val) { // repeatedly go to the left node until reach a parent of a valid node
		if (x & 1)
			x >>= 1;
		else
			--x;
	}
#endif

	while (x < n) { // find the rightmost leaf with value less than `val`
		x = x * 2;
		if (t[x + 1] < val) ++x;
	}

#if not METHOD_1
	if (x == n * 2 - 1) return -1;
#endif
	return x - n;
}

Lazy propagation + find nearest previous element smaller than value

• Method 1:
  • Remember to push before find the ancestor of the target node.
  • The first step is the same.
  • In the second step (find the rightmost leaf with value less than val), it's necessary to push before going to a child node.
• Method 2: It's no longer possible to just go to the nearest left node, because in this image

Assumes the starting node is 26, and all lazy values of ancestor nodes of 26 are applied. The nearest left node is 25, however the lazy value of its parent, node 12, is not applied.

Instead, it's necessary to go to the left child (12) of the nearest ancestor (6) for which the current node is in the right branch; or node 1 in case there's no such node (when the current node is in the leftmost path — 1, 2, 4, 8, 16). The complete code is:

(assumes that push is only for the current node and push_all is for the current node and all its ancestors)

int previous_less_than(int x, int val) {
	x += n;

#if METHOD_1
	int l = n, r = n + x + 1;
	push_all(l); push_all(r - 1);
	
	int found_node = -1;
	for (; l < r; l >>= 1, r >>= 1) {
		if (l & 1) {
			if (t[l] < val) found_node = l;
			++l;
		}
		if (r & 1) {
			--r;
			if (t[r] < val) {
				found_node = r;
				break;
			}
		}
	}
	if (found_node < 0) return -1;
	x = found_node;
#else
	push_all(x);

	while (t[x] >= val) { // repeatedly go to the left node until reach a parent of a valid node
		if (x & 1)
			x >>= 1;
		else {
			x >>= __builtin_ctz(x);
			if (x > 1) --x;
		}
	}
#endif

	while (x < n) { // find the rightmost leaf with value less than `val`
		push(x);
		x = x * 2;
		if (t[x + 1] < val) ++x;
	}

	if (x == n * 2 - 1) return -1;
	return x - n;
}

You can prove that, at any time t[x] is accessed, then all ancestors of x (excluding x) have lazy value pushed.

2D segment tree

Assumes the array size is n*m.

1. If n*m fits in memory, then it's possible to make the segment tree array (2*n)*(2*m) and turn the for loop into two of them (briefly mentioned in this comment
2. Otherwise, if offline processing is available, then just prepare the list of touched element for each 2*n node, build a segment tree for each of them, then process normally.
3. Otherwise, it's necessary to use pointers (dynamic node creation) anyway and non-recursive implementation is not possible.

Segment tree with correct node order

Used when it's necessary for node 1 to be the combined value of all nodes and the combiner function is non-commutative. (usually it's not worse asymptotically to use query(0, n))

• Method 1. Just extend the array to the nearest power of 2.

int floor_pow_2(int x) {
	return 1 << (31 ^ __builtin_clz(x));
};
int ceil_pow_2(int x) {
	return floor_pow_2(2 * x - 1);
}

• Method 2. Store the elements in position $$$x, x+1, ..., 2n-1, n, n+1, ..., x-1$$$ where $$$x$$$ is the largest power of 2 $$$\leq 2n$$$. In that case in order to get the node index from the array index it's not just a simple += n but it's necessary to do this:

vector<int> t(2 * n);
int const offset = floor_pow_2(2 * n); // or ceil_pow_2(n)

int index_to_node(int x) { // note: index_to_node(0) == index_to_node(n) unless n is a power of 2
	x += offset;
	if (x >= 2 * n) x -= n;
	return x;
}

Also, because the node l and r may be on different "layer" it's necessary to modify the range update/query function: (the single index update/query function can stay the same, with p += n replaced with p = index_to_node(p))

void add_range(int l, int r, int val) {
	if (l == r) return; // required otherwise add_range(0, 0) will be the same as add_range(0, n) for n not a power of 2
	l = index_to_node(l);
	r = index_to_node(r);

	auto const processl = [&] {
		if (l & 1) t[l++] += val;
		l >>= 1;
	};
	auto const processr = [&] {
		if (r & 1) t[--r] += val;
		r >>= 1;
	};
	if (l >= offset and r <= offset) processl();

	while (l < r) {
		processl();
		processr();
	}
}