vlado's blog

By vlado, history, 9 months ago, In English,

Okay, so I've found a few resources on segment trees. I know how the most basic stuff works (range sum query and individual element updates, range maximum query, etc), I know how to implement a basic segment tree with those things. But still, I haven't found a single problem I can solve with a segment tree, because they all seem to difficult to me. None of them are simple RMQ problems, most of them either need advanced stuff like range updates, or they are too hard for me because they require some trick, or using something other than an integer as the tree value, or using a modified query, etc. I don't know how to do any of these things since I have no experience, so could anyone link me to some simple problems?

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

+1
I too picked up this topic to learn several times but gave up each time facing the same issues. Looking forward for some good suggestion by experienced programmers.

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Here are some simple problems on segment tree

Array Queries

Curious Robin Hood

HORRIBLE(Need to know Lazy propagataion(Range Update))

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You can start solving problems from A2OJ(they are sorted according to difficulty) or you can follow blog 1 or blog 2. First they will explain segment tree then solve few problems related to segment tree in detail.

»
9 months ago, # |
Rev. 3   Vote: I like it +19 Vote: I do not like it

TL;DR: find the easiest problems you can (like from the A2OJ link in the other answer) and if you can't solve those, look at the editorials, and implement it. Rinse and repeat until you can solve on your own. That being said, I talk about learning DS/Algos in general in my full comment, and I personally think it's worth the read.

I'll answer your question a little more generally, i.e. "How do I get familiar with x data structure/algorithm", since the way you seem to be viewing this problem will cause you to have a similar problem for most other DS/Algos you try to pick up. Apologies if I sound rude, as this is not my intention; I am just trying to help.

So, I think broadly, competitive programming problems can be described as having two components to them:

1 — Problem solving skills/insights

2 — Knowledge of data structures/algorithms

A good problem will have a nontrivial amount of 1, and a nontrivial amount of 2. A strong competitor will also have a lot of experience with 1, and a lot of experience with 2. Personally, I know that I tend to focus on improving 1 more often than 2 (e.g. I didn't learn any string algorithms or even LCA until I got to purple, both of which I probably should have known beforehand). Certain online judges will focus more on 1 than on 2, and vice versa (AtCoder, for example, is almost entirely focused on 1. I've never seen an AtCoder Grand Contest that used any algorithm that wouldn't be found in a Div2C on Codeforces, but their problems can be really hard).

However, very few problems will entirely focus on 2, and have very little focus on 1. This is the problem I believe you are running into, especially with your comment "None of them are simple RMQ problems". If you think about it, this makes sense. If you literally just had a problem that gave you an array, and a bunch of update and range max queries, that wouldn't be much of a problem, would it? That "problem" would be equivalent to a question saying "do you have an implementation of a segment tree that you know how to use?", which is honestly not a very fun question. For people who have segment tree implementations, that question is about as worthwhile as "given two integers, output their sum."

When you are learning a new DS/Algo, and you are doing practice problems, your goal should be to reduce the problem you're given to the "simple RMQ" problem. Sometimes, tricks you've done in other problems will be helpful, and sometimes they won't. I'll give two examples that I personally have faced. There was a problem in one CF contest that I was able to reduce to LCA, but I had never actually gotten around to getting an LCA implementation. This was an example of having 1, but not having 2. When I was learning flow for ICPC, I knew the algorithm, and had done the "simple" problems with it, but if I looked at any flow problem, I had no idea where to start. The set of tricks for flow problems seemed completely different (this, by the way, seems similar to your current situation with segment trees). For me, what ended up working was to look at a problem, try it out for about an hour, fail, look at the editorial, and try and implement the solution after referring to the editorial as few times as possible. Then, I would repeat for 3/4 problems, and then stop giving up on future problems.

When learning a new DS/Algo, there are two major things to pick up from it.

The first is what you can do with this new DS/Algo. In the case of the segment tree, it is the following: for any associative binary operator , we can find the value of that operator applied to a segment (l, r) in time (assuming it takes O(1) to compute on two numbers), and we can update the value of an element in time. The most common instances of this are XOR and addition.

The second is what technique was applied to build that algorithm in the first place. For segment trees, this is divide and conquer. People often neglect this part of learning a DS/Algo, but it is very important. For example, people often learn that merge sort can be used to sort an array in , but don't bother thinking about how it is a useful instance of divide and conquer. In fact, this exact same type of divide and conquer strategy can be used to calculate the inversions of an array in , and the implementation is much cleaner than the compression+fenwick tree approach most people use.

Once you become intimately familiar with both of these aspects of the DS/Algo, you will typically become able to solve a wide range of problems with it, including modifications (for example, if you don't actually understand how a segment tree works, you probably won't be able to solve this problem, because it involves actually interacting with the innards of the data structure).

So, to summarize, keep reading editorials and solving easy problems with it (e.g. on the A2OJ link another user posted), and learn what it is actually doing, and what the common tricks are that involve the DS/Algo. Then, move to harder problems and try to solve them yourself.

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

    Thank you for such a comprehensive reply, I'll make sure to use this for segment trees and any other data structures I'll be learning.