limbo16's blog

The Curse of Segment Tree
By limbo16, history, 6 weeks ago, translation, In English

Hi guys! Today I had an exam on algorithms and data structures, where one of the tasks was to write down an algo for finding longest common increasing subsequence in $$$O(n^2)$$$ (yeah, using pen and paper...) For whatever reason, I came up with only $$$O(n^2logn)$$$ solution. However, this solution could be easily simplified to $$$O(n^2)$$$ and many students from my course wrote this algorithm. I guess it happened because when you don't know segtree it is much easier to avoid wrong paths and reach good solution.

Then I caught myself on the thought that in many problems before I also implemented very dumb overkilled solutions with segment tree simply because I know this data structure (thank god I don't know treaps that well). Then I came up with the name of this phenomenon: "The Curse of Segment Tree". So I wonder have anybody also stumbled with this "curse"? (or I am the only orange guy who cannot come up with stupid dp on the uni exam TᴖT)

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

»
6 weeks ago, # |
← Rev. 2   Vote: I like it +73 Vote: I do not like it

The curse is real! I can't count the number of times I've overkilled a problem with segment trees, when arrays or smtn will work just fine. I think I have become less creative after learning some of these data structures.

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

You wrote a whole segment tree with pen and paper? That's actually legendary if your code ran without any bugs.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

The curse is so real, I have implemented many O(n) solution in nlogn just because I can use segment tree in them (this has been the cause of TLE so many times because my implementation of seg tree runs really slow). At this point I don't even write line sweep anymore, I just spam seg trees.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

The curse is real!

I think I have "The Curse of Treap", because I spam treap everywhere I can. Like yesterday I solved this recent LC problem using two treaps and an algorithm for finding kth ordered statistic of two sorted arrays in $$$O(\log(n))$$$, resulting in $$$O(n \log^2 (n))$$$ abomination, while there are exists $$$O(n)$$$ $$$10$$$-line solution :/

→ Reply
»
6 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Find the min of an array using LiChao Tree in O(NlogN)! Use Aliens' Trick against a range DP problem with N,K <= 100! Find the min weight edge on path between 2 nodes on tree with Kruskal Reconstruction Tree + 2D Sweep Line! Stop using Binary Search, only use Larange Relaxation! Use generating functions to calculate the n-th fibonacci number (n<=50)! Solve Xenia and Tree using a combination of 2D Presistent Segment Tree, Splay and LCT! The possibilities for overkilling are particularly infinite!

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it +57 Vote: I do not like it

This is a real thing. And it can be formulated as "general solutions are not always good"

This is why many coaches advocate to not rush with teaching your students std::sort, std::set / std::map, later segment tree and later treap. Because it is very easy to hook a student into "scripting language mentality" where everything can be solved with a bunch of sets and maps. In short term this will work extremely well giving a boost of performance as the student will be able to solve many new problems that were not easy to solve for him before knowing about set and map. But in a longer term it will be very hard to persuade this student that maps are not the ultimate and universal solution without exposing him to very hard tasks.

There are real stories that some red guy was actually stuck with TL on his coordinate compression solution with a bunch of std::map without any idea how to improve it.

The same thing can also happen with any general concept that is good enough for 95% situations (and 99.9% of real world software engineering situations) but carries some performance loss that can be crucial and that makes it worse than problem-specific solution.

There are plenty of examples for it:

std::map instead of arrays for small integer keys

std::sort instead of std::merge

std::sort instead of linear std::nth_element and std::partition (or even instead of std::max_element)

std::map instead of std::sort + std::lower_bound when all keys for the map are known beforehand

std::multiset instead of std::priority_queue

In general sets and maps instead of linear data structures like arrays, stacks, queues, bitsets.

Almost any data structure construction with "insert N times" pattern is not optimal at least by constant factor, but often it is asymptotically worse.

Dijkstra and Prim implemented in $$$O(m \log n)$$$ instead of $$$O(n^2)$$$ on adjacency matrix when $$$m = O(n^2)$$$

Segment tree or std::multiset instead of FIFO queue with support of some operations (like maximum element) for scanline solutions and for two pointer solutions.

Using hashes when alternative is known, does not hurt efficiency, and is not hard to implement.

More general and more heavy versions of binary tree structures instead of lighter ones when extra operations are not used. Segtree instead of Fenwick tree (aka binary indexed tree). Treap instead of segtree.

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

    I once encountered this solving this problem 1800D - Remove Two Letters, took me 40 minutes to implement hashing. After the contest I looked at my friend's submission and saw that his code was just a few lines.

    The curse is so real even with other techniques, not just Segment trees.

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

    I'd say that std::map (or python dict, or literally anything of the kind) is generally easier to reason about than more efficient techniques, and it's drastically easier to use.

    By the way, C++23 introduces std::flat_map, which might be a nice option, especially if you need to store a lot of maps with few elements each.

    As for established algorithms, you definitely should know your options beforehand (for example, just how easy coordinate compression is).

    → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

this is what my teacher used to say: don't learn segment trees, they are a creativity killer, and you'll be better off without it, that's also one of the main reasons they'll teach it in the third year of INOI

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Yeah for me these are multisets

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I got hacked 2 contests ago because I used segment tree instead of prefix sum, the curse is real

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

ABSOLUTELY REAL. I used segtree in :D of Div3 :(, and idk why it was just prefix sum, but what occurred to me at that moment was only one method. And this has happened multiple times. Sometimes changing the segtree according to question leads to debugging problems and wastes a lot of time.

So even tho I'm not high rated, I sometimes want to forget segtree for this reason :(.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

I learned treap in preparation for IOI 2011. It was exciting. On both competition days I ended up implementing treap for some task before realizing it doesn't actually work and throwing implementation into the bin.

It's real. You learn some new shiny and powerful thing and want to use it everywhere regardless of whether it makes sense or doesn't.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +72 Vote: I do not like it

If you have a hammer, everything looks like a nail.

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

I once learnt lazy segment trees, and euler tour, and then took a round, which resulted in this abomination. Oh well, at least it has better complexity than the intended solution (although a simple dfs is even faster than this).

→ Reply
»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I have used segment tree to solve B,C & D problem of a Div 2 round, and in none of the questions segment tree was needed. The curse is real!

→ Reply
»
6 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

Be like franv, use a Li-Chao tree instead of a queue.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +105 Vote: I do not like it

These are actually two broad levels of segment tree mastery:

  • learn to use segment tree
  • learn to not use segment tree
→ Reply
»
6 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it

My solution is pretty simple: I don't have prewritten code at all.

So I think carefully, before I start to actually writing a segment tree.

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

In China, we use a very cool data structure and faster than segtree and we call it "cat-tree"... Curse of segment tree scares me

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

Polynomial hashing and some other things with a Segment tree :clownglasses:

251757155

→ Reply
»
6 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Wait until you learn what a rage tree is.

→ Reply
»
6 weeks ago, # |
← Rev. 3   Vote: I like it +27 Vote: I do not like it

I think it happens ,and not only segment tree for easy problem where a bs can suffice, generally when you learn a new data structure or technique like dp. There's an inclination to overkill problems by, even easy ones. In the past recent rounds, I saw solutions over killing div3 C with a sparse table and it had been an easy two pointers 15 line code. Besides, the guys who overkill obvious greed problems by dp also.

→ Reply
»
6 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

When I actually understood how to use divide and conquer in custom solutions, I spent some months solving problems with an extra log because I wouldn't stop to think if it was actually necessary in the solution.

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I also wrote a Tree of Segments several times instead of prefix sums or minimum/maximum

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

A very recent example of a guy solving my problem under the curse
https://codeforces.com/blog/entry/115892?#comment-1128582

→ Reply
»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Can you tell me the O(n^2) algorithm

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

I'm an Olympiad student, and the teaching path of our teachers was:
1. basic stuff (cin, cout, variable,...)
2. sortings
3. divide and conquer
4. dp
5. graph algorithms (dfs/bfs/dsu/dijkestra /...)
6. strings algorithms (kmp,lcp,...)
7. segment tree
as you see, segment is the last one. and they told us: if we teach you segment, it will kill your creativity, and you won't think properly. " if dp is a King-key that opens every door, then segment-tree is an axe that breaks that door "

→ Reply
»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Hell, a few days just before this blog post, I took the syndrome to the curse of SQRT-decomposed segment tree, on a freaking 1900-rating problem requiring just merge sort tree.

Yeah, that feel when you have an overpowered tool, and you would try to fit it into anything so you didn't need to spend your brain power to think.

→ Reply
»
5 weeks ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

learning to use a tool is just practice, but learning when not to use the tool is art, when I learned binary search, and started solving problems, a while after that without knowing they required binary search I always came up with binary search AC solutions and they ofc ACed, but after reading the editorial, etc, I saw non-binary search solutions which are easier to come up and the old me probably would've come up with them, also dp too, counting the times I overkilled a simple traversing/2p/greedy problems with dp is uncountable, but after a while, you learn when to not overuse them, personally when I faced problems I was like: is it binary searchable? NO/YES if NO is it dp? ...

now I'm: what if I sort it is it beneficial? Is there any relationship between the answer and the current iterator? can I 2p?, is there any greedy-like way that may AC? Is it possible to dp? Is it possible to binary search?

I do the reverse order now, it may need more time, but it's easier to implement sometimes, etc

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

So do I. I even used a segment tree when I can use just a single variable instead!

But I eventually use a variable instead, so maybe it's not-so affected to me.

And also, I think "The Curse of Segment Tree" is a bad phenomenon because you may spend a lot of time on writing a segment tree but there is a better way!

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I missed the t-shirt of Meta Hacker Cup because I decided to use a segment tree where the problem only required prefix sums :')

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This curse is very real. Everyone I know has tried overkilling every single problem with a segment tree for a few weeks after they learn it. It happened to me too. (My recent overkill segment tree on contest: https://codeforces.com/contest/1935/submission/249808636)

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Real. I forgot about sliding minimum by multisets (1941E - Rudolf and k Bridges, I don't understand deques) and inserted 200 lines of code that could be replaced by a simple multiset!!!

Spoiler
→ Reply