Contact Form Submission - Suggestion (Persistent Data Structures)

cpinitiative / usaco-guide

A free collection of curated, high-quality resources to take you from Bronze to Platinum and beyond.

https://usaco.guide

Other

1.61k stars 483 forks source link

Contact Form Submission - Suggestion (Persistent Data Structures) #3118

Open maggieliu05 opened 1 year ago

maggieliu05 commented 1 year ago

Someone submitted the contact form!

URL: https://usaco.guide/adv/persistent?lang=cpp Module: Advanced - Persistent Data Structures Topic: Suggestion Message: Closest Equals problem from cf is solvable with normal segment tree

bqi343 commented 1 year ago

True, this problem (and application 2) probably shouldn't be part of the module. Also, for application 1 it should be noted that

persistent segment tree is needed only if the queries are online.
persistent segment tree isn't necessarily harder to implement than 2D Fenwick tree, and it's also faster ( $O(\log N)$ vs $O(\log^2N)$ queries).