线段树 BIT 求冒泡排序的交换次数

线段树特别适合与区间相关的运算,比如MRQ(minimum range query)求一段区间内的最小值。 BIT可以看作是压缩了的线段树,由于(某类)线段树的右节点可以由父结点和左兄弟求出来,所以右结点就不用存了。 求冒泡排序的交换次数,直观的想可以直接在冒泡排序的过程中计算交换次数,时间复杂度是O(n^2)。交换次数其实是(位置在j的前面,数值还比aj大的数)j从0到n求和。算法的特点是反复对某一区间内的所有元素求和,可以用BIT来优化。 做法是,i从0到n遍历,在循环的某一趟中,dat[ai]表示数字ai的之前出现过的次数,sum(ai)表示在这一趟之前,小于等于ai的数出现的次数。

#include <iostream>
using namespace std;

const int MAX_N = 10000;
int a[MAX_N],n;
int dat[1000000]; // 假定max(a[i])为1000000

//以下是对BIT的实现
int sum(int i){
    int ans = 0;
    while(i>0)
    {
        ans+=dat[i];
        i -= i&-i;
    }
    return ans;
}

void add(int i,int x){
    while(i<=n){
        dat[i] += x;
        i += i&-i;
    }
}

//计算冒泡排序的交换次数
int calu()
{
    cout<<"this is calu"<<endl;
    int ans = 0;
    for(int i=0;i<n;i++)
    {
        ans += i - sum(a[i]);
        add(a[i],1);
    }
    return ans;

}

int main()
{
    cin<<n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cout<<"ans is "<<calu()<<endl;
    return 0;

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

平面上给定n条线段,找出一个点,使这个点到这n条线段的距离和最小。

题目:平面上给定n条线段,找出一个点,使这个点到这n条线段的距离和最小。 源码如下: 1 #include <iostream> 2 #include ...

27340
来自专栏Petrichor的专栏

numpy: np.random模块 探究(源码)

28120
来自专栏计算机视觉与深度学习基础

全排列生成算法:next_permutation

概念 全排列的生成算法有很多种,有递归遍例,也有循环移位法等等。C++/STL中定义的next_permutation和prev_permutation函数则...

24060
来自专栏菜鸟程序员

【Java】随机数详解

26040
来自专栏前端儿

三角形面积

输入每行是一组测试数据,有6个整数x1,y1,x2,y2,x3,y3分别表示三个点的横纵坐标。(坐标值都在0到10000之间) 输入0 0 0 0 0 0表示输...

16320
来自专栏C/C++基础

C++11新特性——range for

很多编程语言都有range for语法功能,自C++11起,终于将这个重要功能加入C++标准中。range for语句,可以方便的遍历给定序列中的每个元素并对其...

10820
来自专栏Leetcode名企之路

【Leetcode】81. 搜索旋转排序数组 II

( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

22520
来自专栏我是业余自学C/C++的

矩阵

14650
来自专栏数据结构与算法

P3391 【模板】文艺平衡树(Splay)

题目背景 这是一道经典的Splay模板题——文艺平衡树。 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区...

42370
来自专栏决胜机器学习

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(六)——数组的相乘、广义表 (原创内容,转载请注明来源,谢谢) 本文接PHP数据结构(五)的内容。 4.2 行逻辑链接的顺序表 行逻辑链接的顺...

48290

扫码关注云+社区

领取腾讯云代金券