Policy Based Persistent BIT

Revision en1, by hahavodox, 2017-10-08 00:47:02

Recently I come acroos a tecnique similar to Polyci based DS, a Policy Based Persistent BIT. To basic idea is to keep the BIT balanced by HLD. Naive algo is O(n^2). But you have to optimise using bitset to make it O(nlog n). You can perform dynamic range update range query and orthogonal range minimum IDA* search easily in O(Nlog N).

Example:http://codeforces.com/contest/869/problem/E

This can be solved with this trick easily combining this with Baby Step Giant Sweep line. Along with persistent 3SAT.

Tags hld, bit, persistence, ds, monopoly, koto kichu pari, safety pin, bitset

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English hahavodox 2018-12-29 12:30:00 4
en3 English hahavodox 2018-12-18 21:35:18 0 (published)
en2 English hahavodox 2017-10-08 01:00:08 16 (saved to drafts)
en1 English hahavodox 2017-10-08 00:47:02 543 Initial revision (published)