AminAnvari's blog

By AminAnvari, 2 years ago, In English,
Discussion of Segment Tree
 
 
 
 
  • Vote: I like it  
  • +174
  • Vote: I do not like it  

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

Thank you MR anvari

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

omG Tnx AA :D

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

This should also help.

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

Segment tree on string: Letter Array

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

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

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

How come i can only see problem names in russian?

  • »
    »
    2 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]

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

      Now you can see problems in English :))

      • »
        »
        »
        »
        2 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?

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

Is 356A — Knight Tournament a segment tree problem?

  • »
    »
    17 months 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

»
2 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 ??

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

»
17 months 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!

»
16 months 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.)

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

760E is also a segment tree problem

»
15 months 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.

  • »
    »
    11 months 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.

»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Segment tree + dp 675E - Trains and Statistic

»
11 months 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.

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

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

»
11 months 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.

»
11 months 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.

»
11 months 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

»
11 months 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.

  • »
    »
    8 months 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.

»
10 months 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

  • »
    »
    10 months 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

    • »
      »
      »
      10 months 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

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

Thanks !! It was very very helpful.

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

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

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

tysm

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

877E — segment tree on tree

»
6 months 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

»
6 months 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.

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

Great effort!!

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

920F - SUM and REPLACE

could solve with segment... :))

  • »
    »
    4 months 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.

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

Easy!

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

»
5 weeks 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.

»
11 days 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 :)

»
3 days 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...