【数据结构】【应用】树状数组与逆序对

1.在序列a上建立树状数组,初始化为全0。

2.倒序扫描给定序列a,对于每个数a[i]

2.1在BIT中查询前缀和[1,a[i]-1],累加到ans中。

2.2执行单点增加,即把位置a[i]上的数加1,同时正确维护前缀和,这表示a[i]又出现了一次

3.ans即为所求

int reverse(){
	int ans = 0;
	for(int i = n;i;i--){
		ans += sum(a[i] - 1);
		add(a[i],1);
	}
}

 

 

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

留下评论

电子邮件地址不会被公开。 必填项已用*标注