When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

RestingRajarshi's blog

By RestingRajarshi, 6 years ago, In English

Hey,

I recently read this blog, about segment tree beats, but it took me a lot of time to understand this. Thus I have written some blogs on my own stating my own understanding of the topic, so that it is closely linked to the original blog, yet so that its a bit easier to understand. I have explained some of the key concepts that I feel were only touched upon in the original blog but was actually important. However, whatever I have written is based on the original article.

This only includes the explanations for the general concept and the proofs of task 1 and task 2 only. However I hope this explains the proof method itself in a better fashion.

I have also tried to prove the first task using the method in task 2. However I dont yet know whether it is actually correct, and if someone points out the flaw then I would remove it from my post.

Also, any improvements can be suggested in the comments and I would try to update them as soon as possible.

concept task 1 task 2

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

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

Auto comment: topic has been updated by RestingRajarshi (previous revision, new revision, compare).