batch_update_technique (772B)
1 # Batch update technique 2 3 Design an algo that takes a batch of [update], amortize it with [background_rebuilding], and use it to design an efficient algorithm 4 - This is a "one-batch algorithm", sometimes you can do a k-batch algorithm and do nesting to get a better complexity 5 6 Video by [thatchaphol_saranurak] at [simons_institute] 7 https://simons.berkeley.edu/talks/thatchaphol-saranurak-university-michigan-2023-08-28 8 9 ## Application: Graph connectedness under edge deletion 10 11 Can be used for [network_reliability] (undirected graph connectedness) under [edge_deletion] 12 13 batch update algorithm: take a [spanning_tree] and represent the other edges like points in 2d following a [tree_traversal] and do [2d_range_reporting] 14 15 Up: [batch_updates], [incremental_maintenance]