标签： 线段树

LeetCode刷题【307】区域和检索 – 数组可修改

2022 年 6 月 29 日 / / 0 Comments

给你一个数组 nums ，请你完成两类查询。

  1. 其中一类查询要求 更新 数组 nums 下标对应的值
  2. 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right

实现 NumArray 类：

  • NumArray(int[] nums) 用整数数组 nums 初始化对象
  • void update(int index, int val) 将 nums[index] 的值 更新 为 val
  • int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]）

 

示例 1：

输入：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]

解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

 

提示：

  • 1 <= nums.length <= 3 * 104
  • -100 <= nums[i] <= 100
  • 0 <= index < nums.length
  • -100 <= val <= 100
  • 0 <= left <= right < nums.length
  • 调用 update 和 sumRange 方法次数不大于 3 * 104 
Related Topics
  • 设计
  • 树状数组
  • 线段树
  • 数组

  • 👍 521
  • 👎 0

    • 树状数组套模板

    class NumArray {

    private FenwickTree fenwickTree;

    public NumArray(int[] nums) {
        fenwickTree = new FenwickTree(nums.length);
        for (int i = 0; i < nums.length; i++) {
            fenwickTree.add(i+1,nums[i]);
        }
    }

    public void update(int index, int val) {
        fenwickTree.add(index+1,val - fenwickTree.queryIndex(index+1));
    }

    public int sumRange(int left, int right) {
        return fenwickTree.rangeSum(left,right+1);
    }


    class FenwickTree{
        int[] arr;
        public FenwickTree(int n){
            arr = new int[n+1];
        }

        public int lowBit(int x){
            return x & (- x);
        }

        public void add(int idx, int num){
            while (idx < arr.length){
                arr[idx] += num;
                idx += lowBit(idx);
            }
        }

        public int querySum(int idx){
            int res = 0;
            while (idx > 0){
                res += arr[idx];
                idx -= lowBit(idx);
            }
            return res;
        }

        public int queryIndex(int idx){
            return querySum(idx) - querySum(idx-1);
        }

        public int rangeSum(int left, int right){
            if (left > right){
                int tmp = right;
                right = left;
                left = tmp;
            }
            return querySum(right) - querySum(left);
        }
    }
}

    LeetCode刷题【剑指 Offer 51】数组中的逆序对

    2022 年 5 月 27 日 / / 0 Comments

    在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

     

    示例 1:

    输入: [7,5,6,4]
输出: 5

     

    限制：

    0 <= 数组长度 <= 50000

    Related Topics
  • 树状数组
  • 线段树
  • 数组
  • 二分查找
  • 分治
  • 有序集合
  • 归并排序

  • 👍 748
  • 👎 0

    • 归并，基本思路李姐

    归并过程可以把代码的注释打开看下，以实际数据来解释说明下

        归并数组： [7, 6, 5, 4, 3]   [32, 11, 8, 2, 1]
    idxL:0
    idxR:3
    2
    idxL:1
    idxR:3
    2
    idxL:2
    idxR:3
    2
    idxL:3
    idxR:3
    2
    idxL:4
    idxR:3
    2
    归并结果： [32, 11, 8, 7, 6, 5, 4, 3, 2, 1]
    -----

    以上数组A[7, 6, 5, 4, 3]、B[32, 11, 8, 2, 1]

    1. 合并的时候，A的第0个7小于B的第0个32，结果第一位插入32，第二位11同样，第三位8同样
    2. A下标0的数字7大于B下标3的数字2，此时7和后面的[2, 1]形成逆序对，逆序对个数加2
    3. 6同样和后面的[2, 1]形成逆序对，逆序对个数加2
    4. [5, 4, 3]也一样，逆序对分别加2
    5. 而在这之前的A数组内部的逆序对，在最开始之前的时候做归并排序
        归并数组： [7]   [5]
    idxL:0
    idxR:0
    1
    归并结果： [7, 5]
    -----

    以及归并数组： [7, 5] [6]和归并数组： [4] [3]，再将这两个合并归并数组： [7, 6, 5] [4, 3]，得到结果[7, 6, 5, 4, 3]，在这个过程中已经计算过了

    class Solution {
    int count = 0;
    public int reversePairs(int[] nums) {
        sort(nums);
        return count;
    }

    public int[] sort(int[] nums){
        if (nums.length<2){
            return nums;
        }
        int[] right = new int[nums.length/2];
        int[] left = new int[nums.length - right.length];
        System.arraycopy(nums,0,left,0,left.length);
        System.arraycopy(nums,left.length,right,0,right.length);
        left = sort(left);
        right = sort(right);
        return mergeArray(left,right);
    }

    public int[] mergeArray(int[] left, int[] right) {
        if (right.length==0){
            return left;
        }
//        System.out.println("归并数组： "+Arrays.toString(left) +"   "+ Arrays.toString(right));
        int[] arr = new int[left.length + right.length];
        int idx = -1;
        int idxL = 0;
        int idxR = 0;
        while (++idx < arr.length){
            if (idxL<left.length && (idxR>= right.length || left[idxL] > right[idxR])){
                arr[idx] = left[idxL];
                idxL++;
                count += right.length-idxR;
//                System.out.println(right.length-idxR);
            }else{
                arr[idx] = right[idxR];
                idxR++;
            }
        }
//        System.out.println("归并结果： "+Arrays.toString(arr));
//        System.out.println("-----");
        return arr;
    }
}