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.

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

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.

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 :/

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!

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.

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

Yeah for me these are multisets

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

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 :(.

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.

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

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).

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!

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

These are actually two broad levels of segment tree mastery:

• learn to use segment tree
• learn to not use segment tree

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.

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

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

251757155

Wait until you learn what a rage tree is.

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.

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.

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

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

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

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 "

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.

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

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!

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

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.net/contest/1935/submission/249808636)

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!!!