Modular Segment Tree with Lazy Propagation

Правка en5, от saketh, 2015-09-26 06:25:57

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:

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en7 Английский saketh 2015-09-26 08:24:17 50
en6 Английский saketh 2015-09-26 06:27:03 42 Tiny change: '3226700]\n' -> '3226700]\n\nLet me know if you have any suggestions!'
en5 Английский saketh 2015-09-26 06:25:57 23 (published)
en4 Английский saketh 2015-09-26 06:22:45 106
en3 Английский saketh 2015-09-26 06:06:03 98
en2 Английский saketh 2015-09-26 06:03:51 4 Tiny change: 'se, 0});\n\n\n~~~~~\n\' -> 'se, 0});\n~~~~~\n\'
en1 Английский saketh 2015-09-26 05:59:55 2463 Initial revision (saved to drafts)