BIT

木上の点に一律の値を足す & 各点の現在値を求める

Quiz npca2015年部誌_木に対する一般的なテク達.pdf p36 Running Away from the Barn (USACO 2012 December Gold) 木上の点に一律の値を足す これをO(logN)でする方法が必要 下図のようなグラフを考える オイラーツアーとBITを使う u, v (depth[u] < depth[v…

2次元(二次元)BITクラス

参考 http://hos.ac/slides/20140319_bit.pdf Code // 実装参照 http://hos.ac/slides/20140319_bit.pdf // 注意 // 1-indexedです struct BIT2D{ VV bit; ll W,H; // widthが先なので注意 void resize(ll w, ll h){ W = w; H = h; // bit[x][y]の順に確保す…