LeetCode——区域和检索-数组可修改

Q：给定一个整数数组 ?nums，求出数组从索引?i?到?j??(i?≤?j) 范围内元素的总和，包含?i,? j?两点。
update(i, val)?函数可以通过将下标为?i?的数值更新为?val，从而对数列进行修改。

示例:
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2) //把3改成2
sumRange(0, 2) -> 8
说明：
数组仅可以在?update?函数下进行修改。
你可以假设?update?函数与?sumRange?函数的调用次数是均匀分布的。

A：
使用线索树。
线索树介绍：线段树是一种平衡二叉搜索树（完全二叉树），他将一个线段区间划分成一些单元区间。对于线段树中的每个非叶子节点 [a,b]，他的左儿子表示的区间为 [ a, (a+b)/2] ，右儿子表示的区间为 [(a+b)/2+1, b] , 最后的叶子节点数目为 N， 与数组下标对应。
线段树的一般包括建立、查询、插入、更新等操作，建立规模为 N 的时间复杂度是 O(nlogn)，其他操作时间复杂度为O(logn)。

class NumArray {
    class SegmentTreeNode {
        SegmentTreeNode lchild;
        SegmentTreeNode rchild;
        int left;
        int right;
        int val;

        SegmentTreeNode(int left, int right) {
            this.left = left;
            this.right = right;
            this.val = 0;
            this.lchild = null;
            this.rchild = null;
        }
    }

    private SegmentTreeNode root = null;

    NumArray(int[] nums) {
        root = buildSegmentTree(nums, 0, nums.length - 1);
    }

    private SegmentTreeNode buildSegmentTree(int[] nums, int left, int right) {
        if (left > right)
            return null;
        SegmentTreeNode root = new SegmentTreeNode(left, right);
        if (left == right)
            root.val = nums[left];
        else {
            int mid = (left + right) / 2;
            root.lchild = buildSegmentTree(nums, left, mid);
            root.rchild = buildSegmentTree(nums, mid + 1, right);
            root.val = root.rchild.val + root.lchild.val;
        }
        return root;
    }

    public void update(int i, int val) {
        update(root, i, val);
    }

    private void update(SegmentTreeNode root, int pos, int val) {
        if (root.left == root.right)
            root.val = val;
        else {
            int mid = (root.left + root.right) / 2;
            if (pos <= mid)
                update(root.lchild, pos, val);
            else
                update(root.rchild, pos, val);
            root.val = root.lchild.val + root.rchild.val;
        }
    }

    public int sumRange(int i, int j) {
        return sumRange(root, i, j);
    }

    private int sumRange(SegmentTreeNode root, int left, int right) {
        if (root.right == right && root.left == left)
            return root.val;
        else {
            int mid = (root.left + root.right) / 2;
            if (left >= mid + 1) {
                return sumRange(root.rchild, left, right);
            } else if (right <= mid) {
                return sumRange(root.lchild, left, right);
            } else
                return sumRange(root.rchild, mid + 1, right) + sumRange(root.lchild, left, mid);
        }
    }
}

LeetCode——区域和检索-数组可修改

原文：https://www.cnblogs.com/xym4869/p/12562979.html