XDEv11's blog

By XDEv11, 3 years ago, In English

Hey, codeforces community, this is my first blog, so your suggestions are very welcome. Also, I am not a native speaker. Please excuse language errors and let me know.

I recently found this blog entry, Efficient and easy segment trees. It's an old post from six years ago, so there might be a proof about this. However, I don't see one by far. That's why I try to write it. Hope it will help someone who wants to know this a little bit more.

Definition

We call a node legal if

  1. It's between n and n + (n - 1). (an array element)
  2. Both its children are legal and represent subarrays of same size. (a combined value from two children)

Otherwise, it's called illegal.

No overlaps

Let $$$[L_i:R_i)$$$ be the left-closed right-open interval of the i-th layer from bottom (a continuous sequence of legal nodes that represent subarrays of same size.). We know that $$$L_0=n$$$ and $$$R_0=2n$$$, and we have $$$L_{i+1}={\Large\lceil}\frac{L_i}{2}{\Large\rceil}$$$ and $$$R_{i+1}={\Large\lfloor}\frac{R_i}{2}{\Large\rfloor}$$$.

We want to prove that $$$R_{i+1}\le L_i$$$. First, the statement holds for $$$i=0$$$ because $$$R_1=n\le L_0=n$$$. Second, assume it holds for $$$i=k$$$ ($$$R_{k+1}\le L_k$$$), then it also holds for $$$i=k+1$$$ because $$$R_{k+2}={\Large\lfloor}\frac{R_{k+1}}{2}{\Large\rfloor}\le\frac{R_{k+1}}{2}\le\frac{L_k}{2}\le{\Large\lceil}\frac{L_k}{2}{\Large\rceil}=L_{k+1}$$$. Thus, by mathematical induction, the statement holds for every $$$i\ge0$$$.

As a consequence, the structure of this kind of segment tree with an arbitrary size is always feasible.

Correctness of modify()

void modify(int p, int value) { // set value at position p
    for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1];
}

It starts from a leaf node and keeps going up to its parent, so we can make sure every legal node associated with this array element has been updated after modify().

Although, some values in illegal nodes have also been changed, we don't use them and don't care anyway.

Correctness of query()

int query(int l, int r) { // sum on interval [l, r)
    int res = 0;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
        if (l&1) res += t[l++];
        if (r&1) res += t[--r];
    }
    return res;
}

Here, we have a loop invariant -- All nodes in $$$[$$$l$$$:$$$r$$$)$$$ are legal.

At the beginning of the loop, it's easy to see it's true if we get the proper parameters.

Every time it enters the loop, l is less than r, and after the two expressions, l is less than or equal to r.

  • If l is less than r and $$$[$$$l$$$:$$$r$$$)$$$ shrinks to $$$[$$$l >> 1$$$:$$$r >> 1$$$)$$$. By definition, a node is legal if both children are legal, so the loop invariant holds.
  • Or if l is equal to r, l >> 1 is surely equal to r >> 1 and the loop is terminated.

Why we get the answer this way? Every time before $$$[$$$l$$$:$$$r$$$)$$$ shrinking to $$$[$$$l >> 1$$$:$$$r >> 1$$$)$$$, if l is a right child or r - 1 is a left child, the values of corresponding array elements are counted into res, and the others are still covered by the interval. At the end, the interval becomes empty, so all array elements in the original interval have already been counted . Moreover, with the loop invariant, no illegal node would ever be counted.

Advantage

  • Compact code
  • Easy to implement
  • No recursion and less computations (very efficient)

Disadvantage

  • Some space ("illegal" nodes) are wasted, so we lost a little benefits from segment tree. There is an mothod that also uses $$$2N$$$ memory and fully use them.
  • Querying some special intervals like $$$[0:n)$$$ are a bit slower than other implementations because it still goes up the tree.

Here is my code with OOP and GP. Thanks for D4nnyLee for collaboration. Feel free for your own usage. For simplicity, I didn't write a build() function. You can just write a loop to set every array element.

// segment tree
// contributed by XDEv11 & D4nnyLee
template<typename value_t, class merge_t>
class SGT {
    int n;
    vector<value_t> t; // root starts at 1
    merge_t merge; // associative function for SGT
public:
    explicit SGT(int _n, const merge_t& _merge = merge_t{})
        : n{_n}, t(2 * n), merge{_merge} {}
    void modify(int p, const value_t& x) {
        for (t[p += n] = x; p > 1; p >>= 1) t[p >> 1] = merge(t[p], t[p ^ 1]);
    }
    value_t query(int l, int r, value_t init) { // [l:r)
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) init = merge(init, t[l++]);
            if (r & 1) init = merge(init, t[--r]);
        }
        return init;
    }
};

For generic reason, I add the third parameter "init" in query() function. Although, you can add a bool or use std::optional since c++17 to avoid this, it's more intricate in my opinion.

Examples of how to use it :

query for sum
query for min

By the way, if you want to do other modifications rather than assignment, you can query that element first and assign its new value or you can change t[p += n] = x in modify() to what you need.

Thanks the original author for this amazing implementation and MikeMirzayanov for the excellent platform.

UPD: My implementation has been changed. (std::function removed)

UPD2: More formal proof about "No overlaps".

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

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

Auto comment: topic has been updated by XDEv11 (previous revision, new revision, compare).

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

Auto comment: topic has been updated by XDEv11 (previous revision, new revision, compare).

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

function<T(const T&, const T&)> merge;

this is bad, std::function is very ineffective. Better make it a template parameter, just like in STL (see std::sort etc)

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

    I rewrote the code as the above and tried this problem in EDU.

    1. In my opinions, a little overheads are not a big deal in CP.
    2. The execution time is exactly the same as before.
    3. It's harder to use.
    auto ld = [](const int& x, const int& y){return min(x, y);};
    SGT<int, decltype(ld)> sgt{n, ld};
    

    Sorry, I can't get it. Can you tell more about your thoughts?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      found some links...

      https://codeforces.com/blog/entry/74684?#comment-589894

      https://codeforces.com/blog/entry/82113?#comment-689237

      In any case, all such templates are useless. You're almost always required to calculate something special, for example, "given array of small integers, sort range l..r for each query". No template can cover all such cases, so you'll end up copy-pasting and modifying this code. Generic implementation actually makes it harder, not easier.

      Oh, and this particular implementation will fail for non-commutative merges.

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

        Okay, I'll try to figure it out.

        I agree, it's not available in every case. However, it's usually enough. At least in my level, the others are seldom encountered.

        I know it's incorrect for non-commutative functions. But, I also consider that they are rare cases, and for simplicity, I don't handle them. You can definitely add a few lines and it'll work.

        Thanks for pointing these out!

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

        I have revised the code to something like std::priority_queue.

        And, about "given array of small integers, sort range l..r for each query", if you mean get sorted elements in [l:r), you can simply write a struct with a count array and a function object for merging. Otherwise, if you mean sort the elements in [l:r), I think it's impossible without modifying the code.

        Thanks again. Please give further comments if any.

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

      Another way is basically wrapping up everything that you need to define for the operations inside another struct, like:

      template<typename T>
      struct M {
          using Type = T;
          inline const static T Id = 0;
          static T op(const T& x, const T& y) { return x + y; }
      };
      

      Then you just need to pass M<whatever> as a template parameter to the segment tree, and nothing else.

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

        Yep, it's another easy way to do this. But what I want is nothing needed to be changed inside the class. Thanks for commenting anyway!

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

          You don't need to change anything inside the segment tree class when passing a struct like that. Full implementation if you want to see it.

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

            Oh, okay. Sorry for misunderstanding. The only downside is that you need to write another struct. It's a nice suggestion though!

            (But I would like to revise my original idea. Without the problem about std::function, it's quite good for me.)

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

This way is easy,but the function of it is not powerful,maybe the meaning of the way is just higher speed.

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

    Sorry, I can't get it. Does "The function of it is not powerful" means lacking of build() or something?

    There are many other usages in the original blog and another blog I found in comments. Nonetheless, the purpose of this blog is trying to show the fundamentals and prove its correctness.

    Whether powerful or not differs from side to side. A compact and efficient code is awesome for easy situations, especially on-site competitions where you have to code everything by hand.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      It's hard to "push down" the tag,that's the reason why we usually follow the traditional way.

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

        Can you explain more about "push down the tag"? Like something in lazy propagation?

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Yes,though it's a segment tree,but it can't modify the segment easily.If you want to do that,your code will be in a mess.And it's also hard to extend.For example,persistence.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It's just like fenwick tree,less functions but higher speed.

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

        Yup, It's still a work of art in my mind.

        And maybe it's a great way to implement a simple 2-D segment tree due to short code?!