Tag LeetCode

基本性质 每个结点最多有两棵子树，左子树和右子树，顺序不可颠倒。

算法描述 You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

简介 Fenwick Tree 又叫二分索引树（Binary Index Tree），是一种树状结构的数组。该数据结构是由 Peter M. Fenwick 在1994年首次提出来的。最初，Fenwick Tree 被设计用于数据压缩，而现今，该数据结构主要用来存储频次信息或者用于计算累计频次表等。 对于普通的数组，更新数组中的某一元素需要O(1)的时间，计算数组的第n项前缀和（即前n项和）需要O(n)的时间。而 Fenwick Tree 可以在O(log n)的时间内更新结点元素，在O(log n)的时间内计算前缀和。