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: Let t[x] be the minimum value in node x. For simplicity, assume the last element of the array is $$$-\infty$$$.

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

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

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

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

Lazy propagation + find nearest previous element smaller than value

Now it's no longer 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:

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

    for (int s = 31 ^ __builtin_clz(x); s > 0; --s)
        push(x >> s);

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

    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();
    }
}