树状数组（右侧小于当前元素个数）_计算右侧小于当前元素的个数 树状数组

参考官方题解学习了树状数组

适用场景：频繁更新数组、查询前缀和（nlogn）

lowBit：计算最低位的1。原码取反后原来的1变为0，0变为1，+1后连续进位，当前最低位的1的位置即为原来的最低位的1。

tree[i]管辖范围：

i为奇数：原数组中nums[i]

i为2^k：0~i前缀和

i为其他偶数：2^(k-1)+1~i

query：查询前缀和

update：逐个更新管辖范围内tree[i]

稀疏数组离散化处理： 排序后求出每个元素的相对大小进行存储 

class bitTree{
private:
	vector<int> tree;
	int treeSize;
public:
	bitTree(int s):treeSize(s),tree(s){}//
	
	int lowBit(int i){return i&(-i);}
	
	int query(int i){
		int sum=0;
		while(i){
			sum+=tree[i];
			i-=lowBit(i);
		}
		return sum;
	}
	
	void update(int i){
		while(i<treeSize){
			tree[i]++;
			i+=lowBit(i);			
		}
	}
};
 
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
		int numSize=nums.size();
		vector<int> c=nums,ret(numSize);
		sort(c.begin(),c.end());
		bitTree t(lower_bound(c.begin(),c.end(),c.back())-c.begin()+2);
		
		for(int i=numSize-1;i>=0;i--){
			nums[i]=lower_bound(c.begin(),c.end(),nums[i])-c.begin()+1;
			t.update(nums[i]);
			ret[i]=t.query(nums[i]-1);			
		}
		
		return ret;
    }
};