socketnaut's blog

By socketnaut, history, 4 years ago, In English,

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 code we had to touch 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:

Let me know if you have any suggestions!

 
 
 
 
  • Vote: I like it
  • +96
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If instead of adding the value v if I want to update the elemrnt i in [L,R] as : i = f(i) // some function of i. Then how can I proceed.

»
3 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

Surprisingly, I didn't see this post before. Actually, I do have templated implementation, that allows even interval operations like adding arithmetic progression and finding sum. Just didn't want to make the blog too complicated.

Example of such usage is here, but probably you need to register and lock the problem to see it: code

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

I have written one too. I wrote it before I saw your post: https://gist.github.com/sharmaeklavya2/99ed35efbb639bbe7d7b46b89b74fea0

I have used different names: Monoid for list elements and Endomorphism for update operations (these are terms from abstract algebra).