Bruteforceman's blog

Memory Efficient Segment Trees
By Bruteforceman, history, 25 hours ago, In English

Segment trees are not as memory efficient as fenwick trees which often becomes the bottleneck of many problems. There has been attempts at reducing the space required to build a segment tree (e.g. iterative implementation takes $$$2N$$$ space instead of $$$4N$$$ space). But there's a very simple solution to this that can asymptotically improve the space complexity (sorry if this is already well-known).

When building the segment tree, we can simply stop the recursion when $$$r - l \leq \lg n$$$. This means the size of the tree is $$$O \left( \frac{n}{\lg n} \right)$$$ instead of $$$O(n)$$$.

Fortunately we can still answer queries (or perform updates) in $$$O(\lg n)$$$ time for most problems. For the internal nodes, we can simply collect the contribution of that node just like usual. For the leaf nodes with range $$$[l, r]$$$, we will have to scan through the original array in $$$a[l \cdots r]$$$ with a loop and calculate their contribution to the query. Since $$$r - l \leq \lg n$$$, the loop still takes $$$O(\lg n)$$$ time. Any range update/query visits only two leaf nodes, so the time required to process the leaf nodes are also $$$O(\lg n)$$$.

This trick may not be that useful if we need only one segment tree in our problem. However, many problems require building multiple segment trees. For example, one common pattern is to create a segment tree for each bit position. Applying this trick to such problems can reduce the space complexity from $$$O(n \lg n)$$$ to $$$O(n)$$$.

Example Problem:

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

»
25 hours ago, # |
  Vote: I like it +11 Vote: I do not like it

Great blog! Can you please share some problems where we construct a segment tree for each bit? Thank You!

→ Reply
  • »
    »
    24 hours ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    242E - XOR on Segment

    → Reply
    • »
      »
      »
      24 hours ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Nice, Thank You!

      → Reply
    • »
      »
      »
      24 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. I'll add this example to the blog!

      → Reply
»
23 hours ago, # |
  Vote: I like it +10 Vote: I do not like it

If you implement seg trees with this midpoint https://codeforces.com/blog/entry/112755 then if you loop over the seg tree in BFS order, the lengths of node segments are non-increasing:

test

Meaning the set of nodes with length >= X will be some prefix of [1, 2 * n)

→ Reply
  • »
    »
    21 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sketch of proof

    induction assumption: the nodes on the i'th row have lengths:

    2^(k+1), ..., 2^(k+1), x, 2^k, ..., 2^k

    with 2^k < x < 2^(k+1)

    then going from the i'th row to the (i+1)'th row:

    • segments of length 2^(k+1) split into 2 childs of length 2^k
    • segments of length 2^k split into 2 childs of length 2^(k-1)
    • the segment of length x splits into childs of lengths:
    1. 2^k, y; with 2^(k-1) < y < 2^k
    2. y, 2^(k-1); with 2^(k-1) < y < 2^k
    3. 2^k, 2^(k-1)

    thus the (i+1)'th row looks like:

    2^k, ..., 2^k, y, 2^(k-1), ..., 2^(k-1)

    with 2^(k-1) < y < 2^k

    → Reply
»
21 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

I still don't really get why space complexity is $$$O(nlogn)$$$ in general?

→ Reply
  • »
    »
    21 hour(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +24 Vote: I do not like it

    Maybe you mean $$$O(\frac{n}{\lg n})$$$? An intuitive way is to think it as building segment tree over blocks (that is, each leaf represent a block in segment tree), where one block have $$$O(\lg n)$$$ elements, then we have $$$O(\frac{n}{\lg n})$$$ blocks and building a segment tree over it require $$$O(\frac{n}{\lg n})$$$ nodes.

    → Reply
    • »
      »
      »
      20 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, I mean the default segment tree xd

      → Reply
      • »
        »
        »
        »
        15 hours ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Space complexity is $$$O(n)$$$ for default segtree

        I think there's a misconception of $$$O(n)$$$ memory for each of the $$$O(\lg n)$$$ levels. But as you go up a level, the memory reduces by half. So at the last level, there are $$$n$$$ segtree nodes, then $$$n/2, n/4$$$ ... $$$1$$$ at the first level. Add it up, and you get $$$2n$$$ nodes.

        → Reply
        • »
          »
          »
          »
          »
          14 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh wait I just understood what the blog said in the end. Thank you

          → Reply
  • »
    »
    21 hour(s) ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    If you mean in the last paragraph, that's an example where you build a segment tree for every bit position. So a regular segment tree will use $$$O(log n \cdot n)$$$ nodes, while the one in the blog uses $$$O(log n \cdot \frac{n}{log n}) = O(n)$$$ nodes.

    → Reply
»
13 hours ago, # |
  Vote: I like it +19 Vote: I do not like it

Nice. To me, it feels like a combination of segment tree and sqrt decomposition ideas.

→ Reply
»
10 hours ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

There were DSA problems that I used something similar, like the SQRT decomposition idea, but only be able to get (or atleast to prove it at most) $$$O(N \log \log N)$$$ complexity.

It is nice to know more about Segment Tree, thanks.

→ Reply