树状数组以及逆序对求解
- 树状数组基础知识
-
- lowbit操作讲解
- 单点更新
- 区间查询
- 树状数组应用之逆序对
-
- 原理
- 题目及代码
- 推荐给大家的一段话
树状数组基础知识 树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于数组的单点修改&&区间求和.
另外一个拥有类似功能的是线段树.
具体区别和联系如下:
- 两者在复杂度上同级, 但是树状数组的常数明显优于线段树, 其编程复杂度也远小于线段树.
- 树状数组的作用被线段树完全涵盖, 凡是可以使用树状数组解决的问题, 使用线段树一定可以解决, 但是线段树能够解决的问题树状数组未必能够解决.
- 树状数组的突出特点是其编程的极端简洁性, 使用lowbit技术可以在很短的几步操作中完成树状数组的核心操作,其代码效率远高于线段树。
文章图片
下面是二进制版本,能看到
更新过程是每次加了个二进制的低位1(101+1 ->110, 110 + 10 -> 1000, 1000 + 1000 -> 10000)
查询过程每次就是去掉了二进制中的低位1(1111 - 1 -> 1110, 1110 - 10 -> 1100, 1100 - 100 -> 1000)
讲解具体实施步骤
lowbit(x)是取出x的最低位1; 具体代码为:
int lowbit(x){return x&(-x);
}
我们知道,对于一个数的负数就等于对这个数取反+1单点更新 此时如果我们要更改A[1],则有以下需要进行同步更新!!!
以二进制数11010为例:11010的补码为00101,加1后为00110,两者相与便是最低位的1
其实很好理解,补码和原码必然相反,所以原码有0的部位补码全是1,补码再+1之后由于进位那么最末尾的1和原码
最右边的1一定是同一个位置(当遇到第一个1的时候补码此位为0,由于前面会进一位,所以此位会变为1)
所以我们只需要进行a&(-a)就可以取出最低位的1了
会了lowbit,我们就可以进行区间查询和单点更新了!!!
文章图片
void update(int x,int y,int n){
for(int i=x;
i<=n;
i+=lowbit(i))//x为更新的位置,y为更新后的数,n为数组最大值
c[i] += y;
}
区间查询 举个例子 :
i=5
C[4]=A[1]+A[2]+A[3]+A[4];
C[5]=A[5];
可以推出: sum(i = 5) ==> C[4]+C[5];
序号写为二进制: sum(101)=C[(100)]+C[(101)];
第一次101,减去最低位的1就是100;
其实也就是单点更新的逆操作
int getsum(int x){
int ans = 0;
for(int i=x;
i;
i-=lowbit(i))
ans += c[i];
return ans;
}
树状数组应用之逆序对 原理 我们想一想,树状数组能够解决哪些问题,求某个区间的数的和,我们能不能将求逆序对的问题向这个方向转化呢?
我们在换一种角度来看看逆序对:对于每一个数,可能和前面的数形成逆序对,也可能与后面的数形成逆序对。那我们化简一下,对每个数来说,我们只考虑其作为逆序对中第二个数的逆序对,然后将这样的逆序对加起来,实际上就是总逆序对个数。为什么呢,因为每个逆序对有两个元素,第一个数,第二个数。我们将逆序对的第二个数的情况都考虑完了,实际上已经考虑完了所有的逆序对。
题目及代码
文章图片
#include
using namespace std;
typedef long long int ll;
const ll maxn=1e5+10;
const ll maxm=1e8+10;
ll n;
ll a[maxm],b[maxm];
ll ans=0;
ll lowbit(ll x){
return x&(-x);
}
void update(ll x,ll val){
for(ll i=x;
i<=ans;
i+=lowbit(i)){
b[i]+=val;
//cout<>n;
for(int i=1;
i<=n;
i++){
cin>>a[i];
ans=max(ans,a[i]);
}
ll cnt=0;
for(int i=1;
i<=n;
i++){
update(a[i],1);
cnt+=i-getsum(a[i]);
//cout<
推荐给大家的一段话 “遇事不决可问春风,春风不语即随本心”的意思是:对一件事犹豫不决,就问春风该如何做,春风给不出答案,就凭自己本心做出决断。“遇事不决可问春风,春风不语即随本心”一句出自网络作家“烽火戏诸侯”的《剑来》,其原文是:“遇事不决,可问春风。春风不语,遵循己心”。 【竞赛|高级数据结构(树状数组以及逆序对求解)】
文章图片
推荐阅读
- 剑指offer|剑指 Offer第 11 天 双指针(简单)
- LeetCode|LeetCode 467. 环绕字符串中唯一的子字符串 -- 动态规划
- C++|蓝桥杯算法提高欧拉函数--复杂度为O(n log n)
- LeetCode编程题解法汇总|力扣解法汇总2044-正则表达式匹配
- 《C++要笑着学》|【C++要笑着学】类和对象 | 初识封装 | 访问限定符 | 类的作用域和实例化 | 类对象模型 | this指针
- c++|c++类的默认成员函数
- C++|C++ 网络套接字编程TCP和UDP实例
- C++|网络套接字编程
- leetcode|剑指Offer-40-最小的k个数--topk问题java解法整理