代码编织梦想

文章首发于:My Blog 欢迎大佬们前来逛逛

前言

在算法竞赛中,求逆序对是一个常见的问题。逆序对是指在一个数列中,如果存在 i < j i < j i<j,且 a i > a j a_i > a_j ai>aj,那么 ( i , j ) (i,j) (i,j) 就是一个逆序对。例如,数列 2 , 4 , 1 , 3 , 5 {2, 4, 1, 3, 5} 2,4,1,3,5 中的逆序对有 ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) (1,3), (1,4), (2,3) (1,3),(1,4),(2,3),总共有 3 3 3 个逆序对。求逆序对的个数是一个经典的问题,可以使用多种算法来解决,其中树状数组是一种非常高效的算法。

树状数组

树状数组(Fenwick Tree)是一种高效的数据结构,用于维护数列的前缀和。树状数组的主要优势在于可以快速对数列进行单点更新和区间查询,时间复杂度均为 O ( log ⁡ n ) O(\log n) O(logn)。因此,可以使用树状数组来计算逆序对的个数。

树状数组求逆序对

假设有一个长度为 n n n 的数列 a a a,现在需要求解它的逆序对个数。可以使用树状数组来实现,具体步骤如下:

  1. 从后往前遍历数列 a a a,对于每个数 a i a_i ai,使用树状数组查询小于 a i a_i ai 的数的个数 x x x
  2. a i a_i ai 加入树状数组,表示 a i a_i ai 已经被处理过;
  3. 由于 a i a_i ai a i + 1 , a i + 2 , ⋯   , a n a_{i+1}, a_{i+2}, \cdots, a_n ai+1,ai+2,,an 都小,因此逆序对的个数可以加上 x x x,表示这些数与 a i a_i ai 组成了逆序对;
  4. 重复步骤 1 1 1 3 3 3,直到遍历完整个数列;
  5. 根据树状数组的结果计算逆序对的个数,并输出结果。 具体实现时,需要使用一个数组 c c c 存储树状数组,其中 c i c_i ci 表示第 i i i 个位置存储的数的个数。树状数组的更新操作和查询操作可以使用以下代码实现:
c++Copy code// 更新树状数组
void update(int x, int v) {
    while (x <= n) {
        c[x] += v;
        x += lowbit(x);
    }
}
// 查询树状数组
int query(int x) {
    int res = 0;
    while (x > 0) {
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}

其中 lowbit(x) 表示 x x x 的二进制表示中最低位的 1 1 1 所对应的值,即 lowbit(x) = x & -x。 最终,根据树状数组的结果计算逆序对的个数,并输出结果。


过程演示:以 5 4 2 6 3 1数组为例,求它的逆序对:

  1. i=6,此时元素为1,首先查询比 1 小的元素的数量:query(0),sum=0;接着维护树状数组:update(1),c[1]=1,c[2]=1,c[4]=1,c[8]=1
  2. i=5,此时元素为3,首先查询比 3 小的元素的数量:query(2),查询到c[2]=1,sum+=c[2],sum=1;接着维护树状数组:update(3),c[3]=1,c[4]=2,c[8]=2
  3. i=4,此时元素为6,首先查询比 6 小的元素的数量:query(5),5可以分解为5和4,因此查询到c[4]=2,c[5]=0,sum+=c[4],sum=3;接着维护树状数组:update(6),c[6]=1,c[8]=3
  4. i=3,此时元素为2,首先查询比 2 小的元素的数量:query(1),因此查询到c[1]=1,sum+=c[1],sum=4;接着维护树状数组:update(2),c[2]=2,c[4]=3,c[8]=4
  5. i=2,此时元素为4,首先查询比 4 小的元素的数量:query(3),3可以分解为3和2,因此查询到c[3]=1,c[2]=2,sum+=c[3]+=c[2],sum=7;接着维护树状数组:update(4),c[4]=4,c[8]=5
  6. i=1,此时元素为5,首先查询比 5 小的元素的数量:query(4),因此查询到c[4]=4,sum+=c[4],sum=11;接着维护树状数组:update(2),c[2]=1,c[4]=3,c[8]=4

在这里插入图片描述

以下是完整的 C++ 代码实现:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
int n, a[MAXN], c[MAXN];
// 计算 x 的 lowbit
inline int lowbit(int x) { return x & -x; }
// 更新树状数组
void update(int x, int v) {
    while (x <= n) {
        c[x] += v;
        x += lowbit(x);
    }
}
// 查询树状数组
int query(int x) {
    int res = 0;
    while (x > 0) {
        res += c[x];
        x -= lowbit(x);
    }
    return res;
}
int main() {
    // 读入数据
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    // 计算逆序对个数
    long long ans = 0;
    for (int i = n; i >= 1; i--) {
        ans += query(a[i] - 1);
        update(a[i], 1);
    }
    // 输出结果
    printf("%lld\n", ans);
    return 0;
}

总结

树状数组是一种高效的数据结构,用于维护数列的前缀和。使用树状数组可以高效地计算逆序对的个数。树状数组的核心思想是利用二进制的特性,通过计算每个数的 lowbit 来实现快速的更新和查询。希望本文能够对你有所帮助。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/jj6666djdbbd/article/details/129677643

树状数组(求逆序对)-爱代码爱编程

一、树状数组是什么 树状数组,又称二进制索引树,英文名Binary Indexed Tree 之前遇到一个求逆序对的题,看了很多题解都只说了这个树状数组,关于怎么实现的全都避而不谈,我研究了一下午,总算搞出个头绪了 一般用来求前缀和,可以把时间复杂度从O(n)降到O(log10 n)非常恐怖,举个例子,假如我们要求从1~1000的前缀和,普通方法需要

树状数组求逆序数_小虎仔的csdn的博客-爱代码爱编程

1、什么是逆序数? 在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序数的总数就是这个排列的逆序数。 2、用树状数组求逆序数的总数 该背景下树

《剑指offer》51--数组中的逆序对[c++]_贫道绝缘子的博客-爱代码爱编程

题目描述 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007 输入描述: 题目保证输入的数组中没有的相同的数字 数据范围: 对于%50的数据,size<=10^4 对于%75的数据

树状数组求逆序对-爱代码爱编程

树状数组求逆序对 任意给定一个集合a,如果用b[val]保存数值val在集合a中出现的次数,那么数组b在[l,r]上的区间和就表示集合a中范围在[l,r]内的数有多少个。 我们可以在集合a的数值范围上建立一个树状数组,来维护b的前缀和。这样即使在集合a中插入或删除一个数,也可以高效的统计。 也就是以前用普通方法维护b[ ]的前缀和,现在用树状数组来维护

树状数组求解逆序对-爱代码爱编程

逆序对 题目描述 猫猫 TOM 和小老鼠 JERRY 最近又较量上了,但是毕竟都是成年人,他们已经不喜欢再玩那种你追我赶的游戏,现在他们喜欢玩统计。 最近,TOM 老猫查阅到一个人类称之为“逆序对”的东西,这东西是这样定义的:对于给定的一段正整数序列,逆序对就是序列中 a[i]>a[j]且i<j的有序对。知道这概念后,他们就比赛谁先算出给

利用树状数组求逆序对-爱代码爱编程

逆序对: ai>aj 且 i<j 。说白了就是一个序列中前面比后面大的对,举个例子: 序列2 1 4 3 2 , (2 1)就是一个逆序对,(4 3)、(4 2)也是。暴力做法: 遍历这个序列,数一下每个元素前面比他大的元素的个数,累加就是最后的结果,举个例子: 序列2 1 4 3 2 第一个元素 2,前面没有元素,结果 = 0 第二个元素 1

树状数组和逆序对-爱代码爱编程

树状数组 #include<bits/stdc++.h> using namespace std; #define MAXN 100100 int n = 0; int a[MAXN] = { 0 }; int c[10 * MAXN] = { 0 }; inline int lowbit(int x){ return x &

树状数组求解逆序对个数(含树状数组的入门)-爱代码爱编程

树状数组求解逆序对个数(含树状数组的介绍) 一.建立树状数组1.单点更新,区间查询2.区间更新,单点查询3.区间更新,区间查询二.树状数组求解逆序对个数1.逆序对是什么?2.怎么用树状数组实现呢? 在学习树状数组求解逆序对前。先简单学习一下树状数组,首先我们先探究4个问题。 1. 什么是树状数组? 见名知意,就是用数组来模拟树形结构。那么又衍生

树状数组+求逆序对-爱代码爱编程

右图圆圈中标记有数字的结点,存储的是称为树状数组的 tree[]tree[]。一个结点上的 tree[]tree[]的值,就是它树下的直连的子结点的和。例如: tree[1]=a1​tree[2]=tree[1]+a2​tree[3]=a3​tree[4]=tree[2]+tree[3]+a4​⋯tree[8]=tree[4]+tree[6]+tre

树状数组求逆序对个数-爱代码爱编程

先给出树状数组的模板: int lowbit(int a) { return a & (-a); } void update(int x, int y, int n) { for(int i = x; i <= n; i ++) c[i] += y; } int getSum(int x) { int

树状数组&逆序对_可然冫的博客-爱代码爱编程

任意给定一个集合a,用t[val]保存数值val1在集合a内出现的次数,那么数组t在[l,r]上的区间和 ∑ i =

树状数组求逆序对的数量_knookda的博客-爱代码爱编程

用树状数组求逆序对 分析 树状数组初始化为 0 。我们可以利用树状数组依次将输入的值所对应的位置改为 1。对于第i个数a[i]来说,若与其能组成逆序对则比它大的数会在i前边加入到数组,此时**1~a[i] 的前缀和 **

数模笔记——论文写作-爱代码爱编程

论文写作 各模块写作要点 数学建模论文的重要性 数学建模论文的写作是数学建模中重要的一个环节。数学建模的论文是参赛队工作的全面总结,也是评委评价建模成绩的主要依据一篇好的论文应该逻辑清晰,在语言表述上清楚,数学符号标记

动态规划算法-爱代码爱编程

一、前言 动态规划是一种常用的算法,在算法领域十分重要,但对于新手来说,理解起来有一定的挑战性,这篇博客将明确步骤来一步一步讲解动态规划到底该如何理解与运用。 二、解析动态规划算法 1.特点 ①把原来的问题分解成了【要点相同】的子问题(这个要点可以和后面讲的状态联系起来理解) ②所有问题都只需要解决一次(解决一次就是只需要由后面所说

代码随想录训练营第四十八天|198.打家劫舍,213.打家劫舍ii,337.打家劫舍iii-爱代码爱编程

198.打家劫舍 题目链接:https://leetcode.cn/problems/house-robber/submissions/ 代码: class Solution { public: int rob(vector<int>& nums) { int n = nums.size();

什么是分布式任务调度?怎样实现任务调度-爱代码爱编程

通常任务调度的程序是集成在应用中的,比如:优惠卷服务中包括了定时发放优惠卷的的调度程序,结算服务中包括了定期生成报表的任务调度程序,由于采用分布式架构,一个服务往往会部署多个冗余实例来运行我们的业务,在这种分布式系统环境下运

go map-爱代码爱编程

map是无序,非线程安全的,若想使用线程安全的map,使用sync.Map 一、map使用 1. 初始化 直接初始化 var m = map[int]int{} m[1] = 1 fmt.Println(m[1]) 使用make初始化(常用)   m := make(map[int]int) m[1] = 1 fmt.Println