search

kmyk / competitive-programming-library

kimiyuki's library for competitive programming with C++
https://kmyk.github.io/competitive-programming-library
MIT License
66 stars 10 forks source link

could you explain what is the difference between your dual segment tree and the regular segment tree? #2

Closed bethandtownes closed 6 years ago

bethandtownes commented 6 years ago

Hi

I like your code very much! But I have trouble understanding the dual segment tree. Could you explain to me what it does?

Thanks!

kmyk commented 6 years ago

The dual one supports updating over a range and reading at (the trivial sum of) a point, and regular segment tree supports updating a point and get the sum of a range. example: http://codeforces.com/contest/1023/submission/41701318 , used to fill ranges with a same value

This is simplified (and essential) version of "lazy-propagation" (see http://se7so.blogspot.com/2012/12/segment-trees-and-lazy-propagation.html etc). Also note that the word "dual" may not be popular, while "segment tree with lazy propagation" often means both of range-update and range-sum.

bethandtownes commented 6 years ago

thanks！