AminAnvari's blog

Segment Tree Problems
By AminAnvari, 6 years ago, In English

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

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

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thank you MR anvari

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

omG Tnx AA :D

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

This should also help.

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

another segment tree & bits

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

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

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

Segment tree on string: Letter Array

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

Hackerrank's advanced level problems on segment trees are nice too. Check them out.

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

I was looking for this everywhere , i think it will be great helpful for me Thank you.

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

How come i can only see problem names in russian?

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

    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]

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

      Now you can see problems in English :))

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        Again they are in russian; Why ?

        UPD You fixed that again, but in my comment it is russian yet,how to fix it?

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

Is 356A — Knight Tournament a segment tree problem?

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

    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

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thank YOU :)

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

This should be updated with the problem links in this post. How can it be done ??

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

Segment Tree & Dp: 629D - Babaei and Birthday Cake

Segment Tree & Heavy Light Decomposition : 117E - Tree or not Tree

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

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

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

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

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

760E is also a segment tree problem

→ Reply
»
5 years ago, # |
  Vote: I like it -13 Vote: I do not like it

This question(570C) can also be solved using segment tree.Here is my solution.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    That's overkill. There exists an easier and faster solution for that problem.

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

Segment tree + dp 675E - Trains and Statistic

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

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.

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

Segment tree + DP problem : D. Babaei and Birthday Cake

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

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.

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

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.

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

This blog contains 20 Segment tree Problems (Easy, Medium, hard) along with there solutions. Hope it helps someone.

http://codeforces.com/blog/entry/46602

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

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.

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

    I solved it using Lazy Propagation, I couldn't find a way without it, I join the request for a non-lazy-propagation solution.

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

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

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

    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.

    for (int i = 1; i <= n; i++){
  b [i] = get (a[i] + 1, n);
  upd(a [i], 1); 
}

    3 Answer will be sum of d [i].

    d[i] — sum of all b [j] what j < i and a [j] > a [i].

    for (int i = 1; i <= n; i++){
  d[i] = get (a[i] + 1, n);
  upd(a [i], b [i]);
}

    Sorry For My English

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

      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

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

Thanks !! It was very very helpful.

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

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

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

tysm

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

877E — segment tree on tree

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

Why the code is showing TLE for Xenia and Bit operation. http://codeforces.com/contest/339/submission/33017272

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

377D - Developing Game

605D - Board Game — segment tree and ...

...

540E - Infinite Inversions does not really require segment tree, Fenwick tree is enough.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Great effort!!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

920F - SUM and REPLACE

could solve with segment... :))

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

    Do you need lazy propagation? That was my idea in-contest but couldn't implement it right.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Easy!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like 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 .

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

    I solved it using merge sort tree. Needed a little bit of optimization though.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem link

Can anyone help me out? I m stuck and not able to find any editorial for it.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like 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:

    1. The shift of the segment

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

    Query will be of two types:

    1. Update a range[qs, qe]

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

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

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

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

One Occurrence

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How is https://codeforces.com/contest/438/problem/D a lazy propagation problem?

→ Reply
»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

This problem also can be solved using segment tree: 101061E - Playing with numbers
I have solved it using segment tree.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

914D

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

877E - Danil and a Part-time Job , good problem about segment tree+tree+Lazy Propagating.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any of those about Persistent Segment Tree?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks! It's really useful.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

356A — Knight Tournament can be solved using set. No segment tree required

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

1179 C

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

1146E — Hot is Cold

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

Lazy Propagation 1114F — Please, another Queries on Array?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good job! Excellent idea for beginners in segment tree

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you so much for the set of tasks!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good job :)

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

DP+segment tree: B. The Bakery

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you, bro.Great work.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thank you so much my segment tree journey started

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone pls give me a bit intuition of using segment tree for 338E — Optimize!

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    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

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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/

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is great

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A easier Problem which uses segment trees also latest : https://codeforces.com/problemset/problem/1234/D

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

brother next time plz upload problems on HLD

→ Reply
»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

"356A — Knight Tournament" problem must be in "Lazy Propagating" section instead of "classic" section.

Without lazy, you'll definitely get a TLE.

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

https://codeforces.com/contest/1478/problem/E

Spoiler

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Much needed problem set. Thanks a lot!

→ Reply
»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks a lot. That's really helpfull.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Educational Round 112 Div 2 Problem E

→ Reply
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks!!!

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Sometimes you don't have to say thanks, it's more annoying than being quiet and stupid.

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

Parenthesis Checking — A good segment tree problem from the recent AtCoder Beginner Contest

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

    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?

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

      In case you still haven't solved it, here are few hints:

      Hint 1
      Hint 2
      Hint 3
      Hint 4
      Hint 5
      Hint 6
      Hint 7
      Still not able to solve?

      Have a nice day ahead :)

      → Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    This is the same problem as Sereja and Brackets mentioned above. You just check if max subsequence is equal to (r-l+1)

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

nothing

→ Reply
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Aww... This is very helpful. I'm just going to strenghthen my skills in segment tree

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply