Here is a modular segment tree implementation with range query and lazy range update. I have borrowed heavily from Al.Cash's segment tree post a few months ago, so first, a big thanks to him!
You can find the code here. The main feature is that it takes template arguments to specify its behavior:
template<typename T, typename U> struct seg_tree_lazy
so that it is usable without any modification to the pre-written code. Instead, it takes a type T for vertex values, and a type U for update operations. Type T should have an operator +
specifying how to combine vertices. Type U should have an operator ()
specifying how to apply updates to vertices, and an operator +
for combining two updates.
As an example, let's see how to use it to support the follow operations:
- Type 1: Add amount V to the values in range [L, R].
- Type 2: Reset the values in range [L, R] to value V.
- Type 3: Query for the sum of the values in range [L, R].
The T
struct would look like this:
struct node {
int sum, width;
node operator+(const node &n) {
return { sum + n.sum, width + n.width };
}
};
And the U
struct would look like this:
struct update {
bool type; // 0 for add, 1 for reset
int value;
node operator()(const node &n) {
if (type) return { n.width * value, n.width };
else return { n.sum + n.width * value, n.width };
}
update operator+(const update &u) {
if (u.type) return u;
return { type, value + u.value };
}
};
Additionally, the constructor takes a value T zero
, the "zero" node, and a U noop
, the "zero" update. If these are not provided, the default constructors for T and U are used. For this particular use case we would write:
seg_tree_lazy<node, update> st(N, {0, 0}, {false, 0});
And we're done! With this example we can see the power of modularization; the amount of additional code necessary to handle these particular queries is very small. You can see the full implementation with I/O here if you want to play with it.
Finally, here are some other usage examples:
- IOI '14 Wall — Problem, Solution
- 580E - Kefa and Watch — 13226700