题目描述

Given an integer array nums, handle multiple queries of the following types:

Update the value of an element in nums.
Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.
Implement the NumArray class:

NumArray(int[] nums) Initializes the object with the integer array nums.

void update(int index, int val) Updates the value of nums[index] to be val.

int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Example 1:

Input
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
Output
[null, 9, null, 8]

Explanation

java

NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // return 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1, 2, 5]
numArray.sumRange(0, 2); // return 1 + 2 + 5 = 8

Constraints:

1 <= nums.length <= 3 * 10^4
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
At most 3 * 10^4 calls will be made to update and sumRange.

朴素算法

最朴素的算法就是弄一个数组保存截止到\(i\)的时候\([0,i]\)的\(nums\)的求和，然后依次更新数组和信息\(sums\)，返回只需要返回\(sums[right] - sums[left-1]\)就行。(这里用\(sums[1,n]\)对应\(nums[0,n-1]\))

class NumArray {
    vector<int> sums;
public:
    NumArray(vector<int>& nums) {
        int n = nums.size();
        sums.resize(n+1);
        for(int i = 0;i<n;++i){
            sums[i+1] = sums[i]+nums[i];
        }
    }
    
    void update(int index, int val) {
        int oldVal = sums[index+1] - sums[index];
        int delta = val  - oldVal;
        for(int i = index + 1;i<sums.size();++i){
            sums[i]+=delta;
        }
    }
    
    int sumRange(int left, int right) {
        return sums[right+1]-sums[left];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * obj->update(index,val);
 * int param_2 = obj->sumRange(left,right);
 */

但问题是，这里是线性时间的修改，会超时！！！！！！！所以我们需要将线性时间的update优化——使用线段树！

线段树思路与算法

线段树 \(\textit{segmentTree}\)是一个二叉树，每个结点保存数组\(\textit{nums}\)在区间\([s,e]\)的最小值、最大值或者总和等信息（这里就保存求和信息）。线段树可以用树也可以用数组（堆式存储）来实现。对于数组实现，假设根结点的下标为 0，如果一个结点在数组的下标为 \(\textit{node}\)，那么它的左子结点下标为 \(\textit{node} \times 2 + 1\)，右子结点下标为 \(\textit{node} \times 2 + 2\)。

建树build函数

我们在结点 \(\textit{node}\)保存数组 \(\textit{nums}\)在区间\([s,e]\)的总和。

\(s = e\)时，结点 \(\textit{node}\) 是叶子结点，它保存的值等于 \(\textit{nums}[s]\)。
\(s < e\)时，结点 \(\textit{node}\) 的左子结点保存区间 \(\Big [ s, \Big \lfloor \dfrac{s + e}{2} \Big \rfloor \Big ]\)的总和，右子结点保存区间 \(\Big [ \Big \lfloor \dfrac{s + e}{2} \Big \rfloor + 1, e \Big ]\)的总和，那么结点 \(\textit{node}\) 保存的值等于它的两个子结点保存的值之和。

假设 \(\textit{nums}\) 的大小为 n，我们规定根结点 \(\textit{node} = 0\) 保存区间 \([0, n - 1]\) 的总和，然后自下而上递归地建树。

那么线段树的数组大小要多大呢？即已知叶子节点个数，求二叉树节点总数：\(n = f(n_0)\)

Binary Tree 性质

对于一棵二叉树, 设叶子节点数为\(n_0\), 度为1的节点数为\(n_1\), 度为2的节点数为\(n_2\)。度为2的节点有2个分支, 度为1结点有1个分支, 度为0的节点有0个分支。则\(n_0 = n_2 + 1\)(公式1)

证明:

度为2的节点有2个分支, 度为1结点有1个分支, 度为0的节点有0个分支。设分支数个数为\(m\)，

\(m=2\times n_2+n_1\)

另外\(m=n_0+n_1+n_2-1\) (每个结点上面对应一个分支，除了根节点上面没有分支)

因此 \(2\times n_2 + n_1 = n_0 + n_1 + n_2 - 1\)

得 \(n_0 = n_2 + 1\)

注：perfect binary tree

A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level.

Examples:

The following tree is a perfect binary tree

plain

               10
           /       \  
         20         30  
        /  \        /  \
      40    50    60   70


               18
           /       \  
         15         30

The following tree is not a perfect binary tree

plain

Complete Binary Tree 性质

假设n为完全二叉树的结点总数, 则有 \(n=n_0+n_1+n_2\)(公式2)

结合公式 1和2 有\(n_0=\frac{n-n_1+1}{2}\)

又因为\(n_1 = 0\)或者\(n_1 = 1\) 只有这两种情况(完全二叉树的性质呀--只有一个分支的节点要么有, 要么没有, 剩下的全是两个分支的节点和0分支的叶子节点)

当n为奇数时(即度为1的节点为0个)： \(n = 2\times n_0 - 1\)
当n为偶数(即度为1的节点为1个)：\(n = 2\times n_0\)

注意这里计算数组（堆式存储）总大小时候有个问题，就是这棵线段树并不是一颗完全二叉树：

比如以[0,10]下标画一颗树就可以发现，这最后一层不是紧密左排列的。最后一层之间会有空隙！！！

java

             [0,10]
         /             \  
      [0,5]          [6,10]      
     /     \         /     \   
   [0,2]  [3,5]    [6,8]  [9,10] 
   /  \    /  \    /   \   /   \    
[0,1] [2][3,4][5][6,7][8] [9] [10] 
 /  \    /  \    /  \  
[0] [1] [3]  [4] [6] [7]

那么如果以left = 2*n + 1,right = 2*n + 2这种完全二叉树去计算下标的话，实际上的所需数组长度要比\(2\times n_0\)要大！！！

最极端的情况为：

在倒数第二层，第一个节点分裂出两个叶子节点，最后一个节点分裂出俩叶子节点，中间全部都是单个的叶子节点。那么此时把这个倒数第二层的叶子节点（总共不超过\(nums.size()\)个）占用最后一层两个虚拟位置的情况下，补全成完全二叉树就应该有不超过\(n_0=2\times nums.size()\)个叶子节点！！！！

所以，总节点数不超过\(4\times n_0\)个。所以数组总数取4*nums.size()

单点修改change函数

当我们要修改 \(\textit{nums}[\textit{index}]\)的值时，我们找到对应区间 \([\textit{index}, \textit{index}]\)的叶子结点，直接修改叶子结点的值为 \(\textit{val}\)，并自下而上递归地更新父结点的值。

范围求和range函数

给定区间 \([\textit{left}, \textit{right}]\)时，我们将区间 \([\textit{left}, \textit{right}]\)拆成多个结点对应的区间。

如果结点 \(\textit{node}\) 对应的区间与 \([\textit{left}, \textit{right}]\)相同，可以直接返回该结点的值，即当前区间和。

如果结点\(\textit{node}\)对应的区间与\([\textit{left}, \textit{right}]\)不同，设左子结点对应的区间的右端点为 m，那么将区间 \([\textit{left}, \textit{right}]\)沿点 m 拆成两个区间，分别计算左子结点和右子结点。

我们从根结点开始递归地拆分区间 \([\textit{left}, \textit{right}]\)。

代码

class NumArray {
private:
    vector<int> segmentTree;
    int n;

    void build(int node, int s, int e, vector<int> &nums) {
        if (s == e) {
            segmentTree[node] = nums[s];
            return;
        }
        int m = s + (e - s) / 2;
        build(node * 2 + 1, s, m, nums);
        build(node * 2 + 2, m + 1, e, nums);
        segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];
    }

    void change(int index, int val, int node, int s, int e) {
        if (s == e) {
            segmentTree[node] = val;
            return;
        }
        int m = s + (e - s) / 2;
        if (index <= m) { //更新左子树
            change(index, val, node * 2 + 1, s, m);
        } else {
            change(index, val, node * 2 + 2, m + 1, e);
        }
        segmentTree[node] = segmentTree[node * 2 + 1] + segmentTree[node * 2 + 2];
    }

    int range(int left, int right, int node, int s, int e) {
        if (left == s && right == e) {
            return segmentTree[node];
        }
        int m = s + (e - s) / 2;
        if (right <= m) {//全部在左边
            return range(left, right, node * 2 + 1, s, m);
        } else if (left > m) {//全部在右边
            return range(left, right, node * 2 + 2, m + 1, e);
        } else {//左右子树都有
            return range(left, m, node * 2 + 1, s, m) + range(m + 1, right, node * 2 + 2, m + 1, e);
        }
    }

public:
    NumArray(vector<int>& nums) : n(nums.size()), segmentTree(nums.size() * 4) {
        build(0, 0, n - 1, nums);
    }

    void update(int index, int val) {
        change(index, val, 0, 0, n - 1);
    }

    int sumRange(int left, int right) {
        return range(left, right, 0, 0, n - 1);
    }
};

复杂度分析

时间复杂度：
构造函数：\(O(n)\)，其中 n 是数组 \(\textit{nums}\) 的大小。二叉树的高度不超过 \(\lceil \log n \rceil + 1\)，那么 \(\textit{segmentTree}\)的大小不超过 \(2 ^ {\lceil \log n \rceil + 1} - 1 \le 4n\)，所以 \(\textit{build}\)的时间复杂度为 \(O(n)\)。
\(\textit{update}\) 函数：\(O(\log n)\)。因为树的高度不超过 \(\lceil \log n \rceil + 1\)，所以涉及更新的结点数不超过 \(\lceil \log n \rceil + 1\)。
\(\textit{sumRange}\)函数：\(O(\log n)\)。每层结点最多访问四个，总共访问的结点数不超过 \(4 \times (\lceil \log n \rceil + 1)\)。
空间复杂度：\(O(n)\)。保存 \(\textit{segmentTree}\) 需要\(O(n)\)的空间。

二叉树

AVL Tree

Red Black Tree

B Tree

Interval Trees

加权图最短路径

背包问题

子序列问题

二维图

题目描述

朴素算法

线段树思路与算法

建树build函数

Binary Tree 性质

Complete Binary Tree 性质

单点修改change函数

范围求和range函数

代码

复杂度分析

题目描述 ​

朴素算法 ​

线段树思路与算法 ​

建树build函数 ​

Binary Tree 性质 ​

Complete Binary Tree 性质 ​

单点修改change函数 ​

范围求和range函数 ​

代码 ​

复杂度分析 ​

题目描述

朴素算法

线段树思路与算法

建树build函数

Binary Tree 性质

Complete Binary Tree 性质

单点修改change函数

范围求和range函数

代码

复杂度分析