树状数组引入—楼兰图腾_acw

题目大意：

a数组为1~n的一个排列。找到ijk，使得ai>aj&&ak>aj这就是一个‘V’。问有多少‘V’和多少倒‘V’。

思路和代码：

V和倒V是一样的做法，现在只考虑V。找点i左边和右边各有多少个点比点i大，两数字相乘即以该点i为最低点的V数量。

但是数据范围是2e5，不能O(n2)去做。所以引入树状数组。

每个点要找到其父节点就要加上lowbit(x),而要走到他的下一段就要一直减去lowbit(x)。

ll tr[N] ;
ll gr[N] , lw[N] ;

ll lowbit(ll x){
	return x & -x ;
}

void add(ll x , ll c){//下标为x的点加上c 
	for(ll i = x ; i <= n ; i += lowbit(i)) tr[i] += c ;
}

ll sum(ll x){//求下标为x的点的前缀和 
	ll res = 0 ;
	for(ll i = x ; i ; i -= lowbit(i)) res += tr[i] ;
	return res ;
}

void solve(){
	cin >> n ;
	ll ans1 = 0 , ans2 = 0 ;
	VLL a(n + 1 , 0) ;
	rep(i , 1 , n) cin >> a[i] ;
	
	rep(i , 1 , n){
		lw[i] = sum(a[i] - 1) ;
		gr[i] = sum(n) - sum(a[i]) ;
		add(a[i] , 1) ;
	}
	
	rep(i , 0 , n) tr[i] = 0 ;
	
	drep(i , 1 , n){
		ans1 += gr[i] * (sum(n) - sum(a[i])) ;
		ans2 += lw[i] * sum(a[i] - 1) ;
		
		add(a[i] , 1) ; 
	}
	cout << ans1 << " " << ans2 << "\n" ;
	
	
}//code_by_tyrii 

小结：

普通树状数组维护数组可以logn单点修改和logn查询前缀和。