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

thank you for this. I was looking for a simpler problem on segment tree.

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 ?

UPDYou 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 - Бабай и пирог на день рождения

Segment Tree & Heavy Light Decomposition : 117E - Дерево или не дерево

Wow! This will be so much helpful to many. Thanks for the effort!

Titles of the problems appear in Russian in this blog post. Is it possible to change to English? (I remember it was in English previously. Maybe some settings changed for me.)

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 - Электрички и статистика

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://codeforces.com/blog/entry/46602

Thanx it was really helpful.

No hints there :'(

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.

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

Thank you for helping, your comments means a lot to me. :-)

Here's my well commented code (to help people who are stuck on this problem) 29129951

Thanks !! It was very very helpful.

Thanks a lot bud. Finally a compilation of segtrees problems in codeforces

tysm

877E — segment tree on tree

Why the code is showing TLE for Xenia and Bit operation. http://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 - Разработка игры

605D - Настольная игра — segment tree and ...

...BFS?

540E - Бесконечные инверсии does not really require segment tree, Fenwick tree is enough.

Great effort!!

920F - SUM и 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://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.

For every query of type 1, calculate the amount of shift needed towards right (this will be x-y). Example: 1 5 12 16. Shift needed towards right is 5-12 = -7. So here our query starts at y-1(index is 0-based) and ends at y+k-1. For a query range shift is same for all the indices. Imagine here indices 11 to 26 are shifted towards right by -7(therefore towards left by 7).

Our segment tree will contain two variables in every node:

The shift of the segment

-1 or 0 denoting the segment has been overwritten by array 'a', 0 if not.

Query will be of two types:

Update a range[qs, qe]

Answer what is b[x]

Lazy propagation works here. At the start of both the queries if the second value of the node is -1 pass the first value to both its children(if they are present) and set both the values of the node equal to 0. Query type 2 returns two variables: the shift; and, the second value of the node(-1 or 0). If it's -1 ans is a[shift+x] else b[shift+x], x should be adjusted to 0-based index. Note: If the second value of a node is 0, first value(the shift of the segment) is always 0.

Link to the code: http://codeforces.com/contest/292/submission/39273711

958C3 - Encryption (hard) ==> dp + segment(bit)

it's a good problem for practice in my opinion :)

can someone please tell me how to build segment tree in knight tournament problem??Your text to link here...

One Occurrence

How is https://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 - Данил и подработка , good problem about segment tree+tree+Lazy Propagating.

Any of those about Persistent Segment Tree?

Thanks for this. Can you please order them from easy to hard. Thank you.

Thanks! It's really useful.

Thank you AminAnvari! Can someone share a list of MUST SOLVE Dynamic Programming Problems on Codeforces?

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

Good job! Excellent idea for beginners in segment tree

Thank you so much for the set of tasks!

Good job :)

DP+segment tree: B. The Bakery

Thank you, bro.Great work.

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

Segment tree and bits https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/shivam-and-expensive-birthday-gift-da58b2f0/

thanks

This is great

https://codeforces.com/contest/803/problem/G

Can anyone explain the logic behind the question 220E — Little Elephant and Inversions ? If possible please also share the commented code. Thanks