Hi :)
These are some segment tree problems on codeforces. Ofcourse it is not complete and I hope we will complete it with your help. And great thank to NikaraBika for helping me.
UPD : more Segment Tree
Classic :
339D - Xenia and Bit Operations
356A - Knight Tournament
459D - Pashmak and Parmida's problem
61E - Enemy is weak
380C - Sereja and Brackets
474F - Ant colony
292E - Copying Data
501D - Misha and Permutations Summation
220E - Little Elephant and Inversions
338E - Optimize!
19D - Points
351D - Jeff and Removing Periods
515E - Drazil and Park
540E - Infinite Inversions
609F - Frogs and mosquitoes
594D - REQ
455E - Function
Lazy Propagating:
52C - Circular RMQ
145E - Lucky Queries
558E - A Simple Task
240F - TorCoder
446C - DZY Loves Fibonacci Numbers
115E - Linear Kingdom Races
438D - The Child and Sequence
121E - Lucky Array
610E - Alphabet Permutations
580E - Kefa and Watch
Segment tree with Vector:
369E - Valera and Queries
610D - Vika and Segments
Offline Query:
301D - Yaroslav and Divisors
500E - New Year Domino
Segment Tree & Dp:
474E - Pillars
597C - Subsequences
56E - Domino Principle
Segment Tree & Bits:
482B - Interesting Array
242E - XOR on Segment
Segment Tree & Tree:
383C - Propagating tree
343D - Water Tree
173E - Camping Groups
276E - Little Girl and Problem on Trees
396C - On Changing Tree
516D - Drazil and Morning Exercise
375D - Tree and Queries
titles are not tag :))
Thank you MR anvari
omG Tnx AA :D
This should also help.
thanks for the link. It was helpful.
another segment tree & bits
Segment tree on string: Letter Array
Hackerrank's advanced level problems on segment trees are nice too. Check them out.
I was looking for this everywhere , i think it will be great helpful for me Thank you.
How come i can only see problem names in russian?
Umm... right now it can't be seen in english, which I believe most of us need, it would be great to show it like this: [problem code] [english name] / [russian name]
Now you can see problems in English :))
Again they are in russian; Why ?
UPD You fixed that again, but in my comment it is russian yet,how to fix it?
Is 356A — Knight Tournament a segment tree problem?
A little bit late ;-) Yes, it is possible to solve it with a segment tree. But instead of updating a single value and querying for ranges, you have to invert it so that you can modify an interval and get access to each element. Additionally you have to make sure that you insert the fights in the reversed order, otherwise some fights will overwrite others. Here is my implementation: 23198751
Thank you :)
Thank YOU :)
This should be updated with the problem links in this post. How can it be done ??
Segment Tree & Dp: 629D - Babaei and Birthday Cake
Segment Tree & Heavy Light Decomposition : 117E - Tree or not Tree
Wow! This will be so much helpful to many. Thanks for the effort!
760E is also a segment tree problem
This question(570C) can also be solved using segment tree.Here is my solution.
That's overkill. There exists an easier and faster solution for that problem.
Segment tree + dp 675E - Trains and Statistic
You can also find many Segment Tree problems on A2 Online Judge. They are ranked by their difficulty, and also including many online judges like codeforces, SPOJ, codechef etc.
Segment tree + DP problem : D. Babaei and Birthday Cake
Can anyone help me with this? I don't know how use a segment tree in order to solve the problem. I solved this using a C++ set. Thanks in advance.
How to solve 459D using a segment tree? I solved it using Fenwick tree but I could not think of a solution using segment tree.
This blog contains 20 Segment tree Problems (Easy, Medium, hard) along with there solutions. Hope it helps someone.
http://mirror.codeforces.com/blog/entry/46602
Thanx it was really helpful.
Shouldn't 292E — Copying Data be under the "Lazy Propagation" section?
If not, how to solve this problem using just classic segment tree?
Nice list, by the way.
I solved it using Lazy Propagation, I couldn't find a way without it, I join the request for a non-lazy-propagation solution.
195948434
How to solve Enemy is Weak Problem using segment tree,I'm not able to understand the editorial.
Links Problem Enemy is Weak
Editorial blogpost
1 Let's use coordinate compression on a[i]. Then we have all the a[i] in the range (0, N].
2 Let's create new array b[MAXN].
b[i] — amount of j what a [j] > a [i] and j < i.
It can be done with Fenwick or Segment tree.
3 Answer will be sum of d [i].
d[i] — sum of all b [j] what j < i and a [j] > a [i].
Sorry For My English
Thanks !! It was very very helpful.
Thanks a lot bud. Finally a compilation of segtrees problems in codeforces
877E — segment tree on tree
Why the code is showing TLE for Xenia and Bit operation. http://mirror.codeforces.com/contest/339/submission/33017272
Use BufferedReader and PrintWriter
Thanks brother :) This is my 1st code using segment tree. I really wanted to learn this.
http://www.spoj.com/problems/CDC12_H/ . Can you help me in this problem. http://www.spoj.com/submit/CDC12_H/id=20755931 . Here is my submission. I am getting TLE in this code also.
377D - Developing Game
605D - Board Game — segment tree and ...
BFS?
540E - Infinite Inversions does not really require segment tree, Fenwick tree is enough.
Great effort!!
920F - SUM and REPLACE
could solve with segment... :))
Do you need lazy propagation? That was my idea in-contest but couldn't implement it right.
no you don't
Easy!
Combi don't comment it.The person who comment it is Flying_Dragon_02
Don't lie dude.
sorry everyone!! I forget to log out so Flying_Dragon_02 can say something.... it's not good. We're just student. This topic's very good for me because I need to improve my skill in IT
Can someone explain , how to solve http://mirror.codeforces.com/contest/459/problem/D using segment tree . I tried to solve it using merge sort tree but got TLE . Then , i could solve it using BIT and map .
I solved it using merge sort tree. Needed a little bit of optimization though.
Problem link
Can anyone help me out? I m stuck and not able to find any editorial for it.
958C3 - Encryption (hard) ==> dp + segment(bit)
it's a good problem for practice in my opinion :)
One Occurrence
How is https://mirror.codeforces.com/contest/438/problem/D a lazy propagation problem?
This problem also can be solved using segment tree: 101061E - Playing with numbers
I have solved it using segment tree.
914D
877E - Danil and a Part-time Job , good problem about segment tree+tree+Lazy Propagating.
Any of those about Persistent Segment Tree?
Thanks! It's really useful.
Thank you AminAnvari! Can someone share a list of MUST SOLVE Dynamic Programming Problems on Codeforces?
https://mirror.codeforces.com/blog/entry/325
356A — Knight Tournament can be solved using set. No segment tree required
1179 C
1146E — Hot is Cold
Lazy Propagation 1114F — Please, another Queries on Array?
Thank you so much for the set of tasks!
DP+segment tree: B. The Bakery
thank you so much my segment tree journey started
Can someone pls give me a bit intuition of using segment tree for 338E — Optimize!
Has anyone solved 375D — Trees and Queries ? It is the last problem mentioned in the Segment Tree and Tree section?
My approach — I flattened the tree with Euler tour and I couldn't figure out the way to compute the answer with MO's algorithm. How with a change in k, can I get a current query answer from my past queries?? Any suggestion or external references are appreciated
I've solved this problem using MO's algorithm. First I've transformed the given tree into an array based on traversal order. Two index for every node. One for starting time another for finishing time. Within the segment lies the others vertexes of it's subgraph Then based on query nodes, I've a range for left and right. Then I ordered them in MO's ordering. In the MO's for add and remove function, I used two counter array. One for counting the appearances of the colors. And number of appearances of number of colors
Hi, thanks for your answer. Can you share the submission with me?
My Submission
https://mirror.codeforces.com/contest/803/problem/G
brother next time plz upload problems on HLD
https://mirror.codeforces.com/contest/1478/problem/E
Much needed problem set. Thanks a lot!
Thanks a lot. That's really helpfull.
Educational Round 112 Div 2 Problem E
Thanks!!!
Parenthesis Checking — A good segment tree problem from the recent AtCoder Beginner Contest
Hey! I just wanted to ask how you kept track of the minimum element in the cumulative sum. I saw the tutorial but didn't really get it. Any hints?
In case you still haven't solved it, here are few hints:
Represent the string as an array --> open brackets = 1 and close brackets = -1
What was the reason behind transforming the string into an array? What advantage does working with numbers have over working with characters? Think...
Working with numbers allows us to perform range sums. But how does it help us here?
Recall the properties of a regular bracket sequence
No.of open brackets == No.of close brackets
Sum of numbers == 0
For every index $$$i$$$ in the regular bracket sequence, the following condition holds true: no.of open brackets on or before index $$$i$$$ $$$ \gt =$$$ no.of close brackets on or before index $$$i$$$
Minimum prefix sum >= 0
What data must we store in the nodes of the segment tree?
Minimum prefix sum of the segment
Sum of the segment
How do we calculate the minimum prefix sum of the range covered by a node using the values of its children?
curr.minpref = min(left.minpref, left.sum + right.minpref);This video from the cf edu section might give you some insights
And what about the sum of the range?
curr.sum = left.sum + right.sum;Pretty self explanatory I guess.
That's it! Open your ide and implement the above discussed logic!
Here's my code
Have a nice day ahead :)
This is the same problem as Sereja and Brackets mentioned above. You just check if max subsequence is equal to (r-l+1)
nothing
I found another problem that uses "Segment Tree on Euler Tour of the tree" to solve it. The problem is 1132G - Greedy Subsequences and the tutorial is https://mirror.codeforces.com/blog/entry/65752.
Thank you man
thanks
how to solve ant colony?
you find gcd of [l,r] with sparse table, and count number of occurences of gcd in [l, r] with a simple pos array, and subtract it from n
i am learning segment trees i tried Knight Tournament here is my solution 269847713 can anyone help i looked at others solution i cot that set approach but i wanted to know what i am doing wrong in segment trees....
Thank you for this!
I wanted to find some recent segment tree problems but couldn't find a list with fresh problems.
From the recent contests this one is neat 2057D - Gifts Order.
Also, look at how jiangly implements segment trees. His tree is templated and operations are generalized so the solution often boils down to defining the node and the associative operation. The same goes for the lazy propagation, where you just need to define how the lazy update is applied.
Why python code gives TLE even if the complexity is O(q*logn)
Also, this problem can be solved using ST