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

Then, we set the leaf values:

vector<node> leaves(N, {0, 1});
st.set_leaves(leaves);

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