perogram

Binary Indexed Tree

BITを2つ使って範囲更新・範囲和 (区間更新・区間和)

使った問題 https://atcoder.jp/contests/abc141/tasks/abc141_c Submisssion https://atcoder.jp/contests/abc141/submissions/7551683 できること 範囲加算 [a, b) にwを加える 範囲和 [a, b)の和を求める (計算量 : それぞれlog(N)) 内部実装 差分をBITで…

座標圧縮とBITで転倒数・反転数を求める

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_D&lang=jp Submit http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3579423#1 座標圧縮とは 大小関係を保ったまま、値のスキマをなくすことで値域を減らす 例 [1, 100, 10000…