【英雄哥六月集训】第 24天: 线段树

系列文章

文章目录

系列文章
树状数组
一、翻转对
二、数组中的逆序对
总结

树状数组

树状数组或二叉索引树（英语：Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和，区间和。

一、翻转对

493. 翻转对

class Solution {
    class BIT{
        int[] tree;
        int n;
        public BIT(int n){
            this.n = n;
            this.tree = new int[n+1];
        }

        public static int lowbit(int x){
            return x & (-x);
        }

        public void update(int x, int d){
            while( x<=n){
                tree[x] +=d;
                x += lowbit(x);
            }
        }

        public int query(int x){
            int ans = 0;
            while(x != 0){
                ans += tree[x];
                x -= lowbit(x);
            }
            return ans;
        }
        
    }
    public int reversePairs(int[] nums) {
        Set<Long> allNumbers = new TreeSet<Long>();
        for(int x:nums){
            allNumbers.add((long) x);
            allNumbers.add((long) x * 2);
        }
        Map<Long,Integer> values = new HashMap<Long, Integer>();
        int idx = 0;
        for(long x : allNumbers){
            values.put(x,idx);
            idx++;
        }

        int ret = 0;
        BIT bit = new BIT(values.size());
        for (int i = 0; i<nums.length; i++){
            int left = values.get((long) nums[i]*2), right=values.size()-1;
            ret +=bit.query(right+1)-bit.query(left+1);
            bit.update(values.get((long) nums[i]) +1,1);

        }
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

二、数组中的逆序对

剑指 Offer 51. 数组中的逆序对

class Solution {
    class BIT{
        int[] tree;
        int n;
        public BIT(int n){
            this.n = n;
            this.tree = new int[n+1];
        }

        public static int lowbit(int x){
            return x & (-x);
        }

        public void update(int x){
            int d=1;
            while( x<=n){
                tree[x] +=d;
                x += lowbit(x);
            }
        }

        public int query(int x){
            int ans = 0;
            while(x != 0){
                ans += tree[x];
                x -= lowbit(x);
            }
            return ans;
        }
        
    }
    public int reversePairs(int[] nums) {
        int n=nums.length;
        int[] tmp = new int[n];
        System.arraycopy(nums,0,tmp,0,n);
        Arrays.sort(tmp);
        for(int i=0;i<n;i++){
            nums[i]= Arrays.binarySearch(tmp,nums[i])+1;
        }
        BIT bit = new BIT(n);
        int ans = 0;
        for(int i = n-1;i>=0;--i){
            ans += bit.query(nums[i]-1);
            bit.update(nums[i]);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

总结

拷贝数组
System.arraycopy(nums,0,tmp,0,n);

相关阅读:
Jenkins（1）基础概念与安装部署简单说明
算法入门篇-STL之Vector，Stack，Queue,list
C++(11)：to_string及stoi
python多线程返回值问题重写Thread类的run方法
【MySQL高级】Mysql的体系结构概览及存储引擎以及索引的使用
LeetCode题目笔记——01.09. 字符串轮转
RabbitMQ 5种工作模式介绍和Springboot具体实现
【算法基础】一文掌握十大排序算法，冒泡排序、插入排序、选择排序、归并排序、计数排序、基数排序、希尔排序和堆排序
linux安装Ftp
linux的美化工具 oh-my-zsh的安装与使用神器工具

原文地址：https://blog.csdn.net/weixin_39348931/article/details/125471557