来自 关于计算机 2019-11-14 16:51 的文章
当前位置: 六合联盟网 > 关于计算机 > 正文

树状数组Binary

leetcode笔记:Range Sum Query - Mutable

大器晚成. 标题陈诉

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

二. 标题解析

标题在Range Sum Query - Immutable生机勃勃题的基础上加码的难度,要求在输入数组nums后,能够修正数组的因素,每回只改良二个因素。同样要促成求数组的有个别区间和的效果与利益。

假诺在乎气风发题的做法上稍加改良,是足以兑现效果与利益的,但是会晚点。

那时阅读了一部分篇章后才发觉原先杰出的做法(包涵前黄金年代题卡塔尔是行使树状数组来维护这几个数组nums,其插入和查询都能成就O(logn)的复杂度,拾分精美绝伦。

三. 示例代码

// 超时
class NumArray {
public:
    NumArray(vector &nums) {
        if (nums.empty()) return;
        else
        {
            sums.push_back(nums[0]);
            //求得给定数列长度
            int len = nums.size();
            for (int i = 1; i < len; ++i)
                sums.push_back(sums[i - 1] + nums[i]);
        }
    }

    void update(int i, int val) {
        for (int k = i; k < nums.size(); ++k)
            sums[k] += (val - nums[i]);
        nums[i] = val;
    }

    int sumRange(int i, int j) {
        return sums[j] - sums[i - 1];
    }

private:
    vector nums;
    //存储数列和
    vector sums;
};


// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);

// 使用树状数组实现的代码AC,复杂度为O(logn)
class NumArray {
private:
    vector c;
    vector m_nums;
public:
    NumArray(vector &nums) {
        c.resize(nums.size() + 1);
        m_nums = nums;
        for (int i = 0; i < nums.size(); i++){
            add(i + 1, nums[i]);
        }
    }

    int lowbit(int pos){
        return pos&(-pos);
    }

    void add(int pos, int value){
        while (pos < c.size()){
            c[pos] += value;
            pos += lowbit(pos);
        }
    }
    int sum(int pos){
        int res = 0;
        while (pos > 0){
            res += c[pos];
            pos -= lowbit(pos);
        }
        return res;
    }

    void update(int i, int val) {
        int ori = m_nums[i];
        int delta = val - ori;
        m_nums[i] = val;
        add(i + 1, delta);
    }

    int sumRange(int i, int j) {
        return sum(j + 1) - sum(i);
    }
};
// Your NumArray object will be instantiated and called as such:
// NumArray numArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);

四. 小结

事先只是听过,那是第贰次采纳树状数组,那是维护数组的一个很好的思索,供给浓郁学习!

Sum Query - Mutable 风流倜傥. 标题陈诉 Given an integer array nums , find the sum of the elements between indices i and j (i j) , inclusive. The update(i, val...

标题建议

有三个数组 nums[0 . . . n-1],大家期待能提供如下八个效益:

  • 功能1:求出前 i 个成分的和 sum
  • 职能2:退换某些元素的值,即nums[i] = x

能够观望,作用1的岁月复杂度为O(n),效率2的时间复杂度为O(1)
本来,为了精耕细作效能1的日子复杂度,大家得以新建四个数组int[] sum,用于记录前 i 个要素的和,即 sum[i] = nums[0] + nums[1] + ... + nums[i]。不过当时,作用2的时辰复杂度变为了O(n),因为须要去维护数组 sum

LeetCode题目:307. Range Sum Query - Mutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.

Example:
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

哪些优化

是否能够在 O(log n) 的小运内到位上述的五个效果与利益?
大器晚成种办法是选择Segment Tree 线段树,具体参见Segment Tree 线段树 原理及落实。

再有大器晚成种方式是利用树状数组Binary Indexed Tree。比较Segment Tree 线段树,它的优势是利用空间越来越小,更易于完成。

树状数组Binary Indexed Tree

动用数组存款和储蓄,假诺为 BITree[],每二个成分存款和储蓄的是原数组 arr[]一点因素的和

叁个异样的位运算:
收获数字 A 的最低有效位:A & -A 或者 A & ~(A - 1)
举例数字 6(110卡塔尔的最低位对应 2(10卡塔 尔(英语:State of Qatar)

撤销数字 A 的最低有效位:A = A - (A & -A) 或者 A = A - (A & ~(A - 1))
比如数字 6(110卡塔 尔(阿拉伯语:قطر‎的最低位对应 2(10卡塔 尔(英语:State of Qatar),祛除后收获 4(100卡塔 尔(阿拉伯语:قطر‎

越多请参见 Bit Manipulation 位运算何足为奇套路及相应LeetCode算法题

基本考虑

每一种整数都能表示为一些2的幂次方的和,比方13,其二进制表示为1101,所以它能表示为:
13 = 1 + 4 + 8 = 2^0 + 2^2 + 2^3 = 1 + 100 + 1000
左近的,储存和可代表为其子集结之和。

i记为BITree的索引(从1开始),r记为i的二进制表示中最左侧的1后边0的个数, 则BITree[i]记为数组中, 索引从(i-2^r +1)i的全数数的和,包涵nums[i-2^r +1]nums[i]
例如:
i = 12 (1100), r = 2, i-2^r +1 = 9, BITree[12] = 第9个元素+...+第12个元素 = nums[8]+...+nums[11]
i = 13 (1101), r = 0, i-2^r +1 = 13, BITree[13] = 第13个元素 = nums[12]
如图所示:

图片 1

image

能够看见,要是必要前13个要素的和:
sum(13) = BITree[13]+BITree[12]+BITree[8] = BITree[1101]+BITree[1100]+BITree[1000]

能够观察,若是要翻新第四个要素的值,会耳闻则诵到七个BITree元素:

  • BITree[3],即BITree[11]
  • BITree[4],即BITree[11 + 1 = 100]
  • BITree[8],即BITree[100 + 100 = 1000]

图片 2

image

求出前 i 个要素的和

    // 求出前 `i` 个元素的和
    public int sum(int i) {
        int sum = 0;

        i++;
        while(i > 0) {
            sum = sum + BITree[i];
            i = i - (i & -i);
        }

        return sum;
    }

求出区间成分的和

    public int sumRange(int i, int j) {
        return sum(j) - sum(i - 1);
    }

转移某些成分的值,即nums[i] = x

    // 改变某个元素的值
    public void update(int i, int val) {
        int diff = val - nums[i];

        nums[i] = val;

        updateBIT(i, diff);
    }

    // 更新树状数组Binary Indexed Tree
    public void updateBIT(int i, int val) {
        i++;
        while(i <= n) {
            BITree[i] = BITree[i] + val;
            i = i + (i & -i);
        }
    }

Binary Indexed Tree的构造

    // 树状数组Binary Indexed Tree
    int[] BITree;

    int[] nums;

    int n;

    public NumArray(int[] nums) {
        this.nums = nums;
        this.n = nums.length;

        // 初始化树状数组Binary Indexed Tree
        // 索引都从1开始
        this.BITree = new int[n + 1];
        Arrays.fill(BITree, 0);

        for(int i = 0; i < n; i++) {
            updateBIT(i, nums[i]);
        }
    }

二维树状数组Binary Indexed Tree

LeetCode题目:308. Range Sum Query 2D - Mutable
Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

图片 3

Range Sum Query 2D

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example:

Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
update(3, 2, 2)
sumRegion(2, 1, 4, 3) -> 10

Note:

  1. The matrix is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRegion function is distributed evenly.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.
class NumMatrix {
    int[][] BITree;
    int[][] nums;
    int m;
    int n;

    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return;

        m = matrix.length;
        n = matrix[0].length;

        BITree = new int[m + 1][n + 1];
        nums = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                update(i, j, matrix[i][j]);
            }
        }
    }

    public void update(int row, int col, int val) {
        if (m == 0 || n == 0) return;

        int delta = val - nums[row][col];

        nums[row][col] = val;

        int i = row + 1;
        while(i <= m) {

            int j = col + 1;
            while(j <= n) {
                BITree[i][j] += delta;

                j += j & (-j);
            }

            i += i & (-i);
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (m == 0 || n == 0) return 0;

        return sum(row2, col2) + sum(row1 - 1, col1 - 1) - sum(row1 - 1, col2) - sum(row2, col1 - 1);
    }

    public int sum(int row, int col) {
        int sum = 0;

        int i = row + 1;
        while(i > 0) {

            int j = col + 1;
            while(j > 0) {
                sum = sum + BITree[i][j];

                j -= j & (-j);
            }

            i -= i & (-i);
        }

        return sum;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * obj.update(row,col,val);
 * int param_2 = obj.sumRegion(row1,col1,row2,col2);
 */

树状数组Binary Indexed Tree的扩展

树状数组Binary Indexed Tree不光可以用来求和,仍可以够求功效。
LeetCode题目:493. Reverse Pairs
Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].
You need to return the number of important reverse pairs in the given array.

Example1:
Input: [1,3,2,3,1]
Output: 2

Example2:
Input: [2,4,3,5,1]
Output: 3

class Solution {
    private int search(int[] BITree, int i) {
        int sum = 0;

        while (i < BITree.length) {
            sum = sum + BITree[i];
            i = i + (i & -i);
        }

        return sum;
    }

    private void insert(int[] BITree, int i) {
        while (i > 0) {
            BITree[i] += 1;
            i = i - (i & -i);
        }
    }

    public int reversePairs(int[] nums) {
        int res = 0;
        int[] copy = Arrays.copyOf(nums, nums.length);
        int[] BITree = new int[copy.length + 1];

        Arrays.sort(copy);

        for (int num : nums) {
            // 先查找在之前的数字中,有多少个val大于等于nums[i] * 2l + 1的数字
            res += search(BITree, index(copy, 2L * num + 1));

            // 再插入该数字
            insert(BITree, index(copy, num));
        }

        return res;
    }

    // 在一个有序数组中搜索
    // For each element, the "index" function will return its index in the BIT.
    // Unlike the BST-based solution, this is guaranteed to run at O(nlogn)
    private int index(int[] arr, long val) {
        int l = 0, r = arr.length - 1, m = 0;

        while (l <= r) {
            m = l + ((r - l) >> 1);

            if (arr[m] >= val) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        return l + 1;
    }
}

引用:
树状数组(Binary Indexed Trees)
Binary Indexed Tree or Fenwick Tree

本文由六合联盟网发布于关于计算机,转载请注明出处:树状数组Binary

关键词: