FenwickTree and Counting Inversions
Not very clever to forget all these.
FenwickTree 树状数组
Common data structure in programming contest to answer range query questions. Simple implementation and less functionalities, $O(n)$extra space, query and edit in $O(logn)$.