【関連】 D - プレゼント (ABC038D - プレゼント - 競プロはじめました) 考え方 回答例 参考 考え方$A$の昇順・$B$の降順で見ていく．絵を書くとわかりやすい．各$B_{i}$に対し， bit[i] += 1とし， ans +=$\sum_{j (\geq i)} \mathrm{bit\,} [j]$としていく…

フェニック木 (Fenwick tree) とも呼ばれます． 基本形（区間和） 機能 実装例 例題 応用（最大・最小・XORなど） 機能 実装例 例題 応用（二分探索→ある要素が何番目に大きいかがわかる） 参考 基本形（区間和）機能数列$a_{1},a_{2},...,a_{N}$があったと…