[力扣493] 离散化&权值线段树,权值树状数组&CDQ分治
题目链接
493. 翻转对
题目描述
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。
样例
数据范围
本题有一个更常见的版本：面试题51. 数组中的逆序对，求数组中的逆序对个数(等价于冒泡排序的交换次数)
此外 315. 计算右侧小于当前元素的个数，327. 区间和的个数。都与本题一样，属于区间内的统计问题，并且都是有以下两种主流的做法，此外还有平衡树的做法：
算法1: 离散化+权值线段树
维护区间信息的线段树，例如区间和，区间最大/最小值，也叫区间线段树。
权值线段树维护元素值的计数，节点的位置代表元素值，节点的值代表元素的数量，其中叶子节点代表特定元素的数量，非叶子节点代表一个取值范围的元素的数量。
每来一个新元素，递归地相应的叶子节点把节点值 +1，然后在回溯阶段把当前节点的值也+1，从根到叶子的路径上的节点值就都被 + 1 了。
离散化
离散化的核心思想：将分布大却数量少(即稀疏)的数据进行集中化的处理，减少空间复杂度。
在统计元素的计数，以及求逆序时的过程中，不关心元素的实际值，只关心元素的大小关系。这样可以用排名代替原数组。流程：排序，去重，取原始数据的排名。
原始数组为 nums, ；排序去重后的数组为 x。则对原始数组中的数据 nums[i]，它的从 0 开始计的排名是
upper_bound(x.begin(), x.end(), nums[i]) - x.begin();
<< · Back Index ·>>
下一篇
相关推荐
【戈尔贡】2038年 燃烧瓶与催泪弹（附机动装甲命名模式）
世界观专栏： 世界地图： 前篇： 戈尔贡的其中一个后续——珀尔修斯： 特别感谢伟大策展者们，他们的存在让想象的世界更多彩 ...
萧亚轩疑似分手，黄皓清空与之有关微博，但她依旧说“谢谢”
作者：梦鹿 原创作品，抄袭必究 #萧亚轩谢谢你你的一切再见# （1）萧亚轩“谢谢，再见” 萧亚轩忽然在凌晨在社交平台上发表伤 ...