树状数组求逆序对

 时间:2024-10-14 06:20:04

逆序对,普通方法数O(n^2)n>=10000就超时了,树状数组可以在O(nlogn)时间内做出。

离散化

1、离散化的思路就是排序,然后就可以将十分大的数变小,而指向位置关系没有变,“逆向”求逆序对,其中,第i个数表示第i大的数在哪

树状数组求逆序对

2、代码如下

树状数组求逆序对

求值

1、先给大家看看代码:

树状数组求逆序对树状数组求逆序对

2、为什么是这样写?我们来模拟一下。

树状数组求逆序对

3、其实这个树状数组的结点记录的是≤它的数量,其中,大于的=当前总数-小于等于的,下图表示每个结点的“贡献”

树状数组求逆序对

4、把这两段结合起来,就是一个完整的代码

树状数组求逆序对
  • 如何确定需求测试的要点?
  • winsock建立连接
  • Eclipse如何用aptana模拟用户注册信息提交校验
  • win10怎么在桌面创建一个笔记或者便笺
  • 如何java获取当前日期
  • 热门搜索
    书香伴我行手抄报 历史手抄报图片大全 向国旗敬礼手抄报图片 壮族三月三手抄报 安全健康手抄报 以书为友手抄报 有关文明的手抄报 有关保护环境的手抄报 数学手抄报内容六年级 关于数学的手抄报内容