leet-code 307. 区域和检索 - 数组可修改

「爱情、让人受尽委屈。」 2022-02-26 12:22 140阅读 0赞

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

示例:
    
     Given nums = [1, 3, 5]
     
     sumRange(0, 2) -> 9 update(1, 2) 
     sumRange(0, 2) -> 8

> 说明:
> 
> 数组仅可以在 update 函数下进行修改。 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

思路:解决这道题可以用两种方法,一种是用数组,列次303那道题,加上update方法实现数组的更新,还有一种是使用线段树来解决,因为涉及到更新,线段树的效率明显比数组高不少,更适合这道题,两种方法如下:  
数组方法解决:

public class NumArray { 
        private int[] sum; // sum[i]储存前i个元素和, sum[0] = 0 sum[i]储存nums[0...i-1]的和
        private int[] data;
        public NumArray(int[] nums) { 
            data = new int[nums.length];
            for(int i = 0; i < nums.length; i++) { 
                data[i] = nums[i];
            }
            // 因为有计算前零个nums元素的长度,所以声明sum数组的长度为nums的长度加一
            sum = new int[nums.length + 1];
            // 要记录sum[0],因为这也是一个区间
            sum[0] = 0;
            // 对sum数组的值进行遍历赋值
            for(int i = 1; i < sum.length; i ++) { 
                // 就如此时sum[1]对应的元素和是nums[0],因为sum[0]被占了,这个意思懂吧,所以推导到下面的公式
                sum[i] = sum[i - 1] + nums[i - 1];
            }
        }
    
        // 307. 区域和检索 - 数组可修改(时间长)
        public void update(int index, int val) { 
            if(index < 0 || index > data.length) { 
                throw new IllegalArgumentException("Args Exception");
            }
            data[index] = val;
           for (int i = index + 1; i < sum.length; i ++) { 
               sum[i] = sum[i - 1] + data[i - 1];
           }
        }
    
        // 求i到j区间的和,注意是闭区间
        public int sumRange(int i, int j) { 
            return sum[j + 1] - sum[i];
        }
    
    
    }

线段树方法高效解决:

/** * @author BestQiang */
    public class SegmentTree<E> { 
        private E[] data;
        private E[] tree;
        private Merger<E> merger;
    
        public SegmentTree(E[] arr, Merger<E> merger) { 
    
            this.merger = merger;
    
            data = (E[]) new Object[arr.length];
            for(int i = 0; i < arr.length; i++) { 
                data[i] = arr[i];
            }
            tree = (E[]) new Object[4 * arr.length];
            buildSegmentTree(0, 0, data.length - 1);
        }
    
        // 在treeIndex的位置创建表示区间[l...r]的线段树
        private void buildSegmentTree(int treeIndex, int l, int r) { 
            if(l == r) { 
                tree[treeIndex] = data[l];
                return;
            }
    
            int leftTreeIndex = leftChild(treeIndex);
            int rightTreeIndex = rightChild(treeIndex);
    
            // 下面这种取中间值的做法在取得数特别大的是后续可能会导致整形溢出的问题,所以不采用
            // int mid = (l + r) / 2;
            int mid = l + (r - l) / 2;
            buildSegmentTree(leftTreeIndex, l, mid);
            buildSegmentTree(rightTreeIndex, mid + 1, r);
    
            // 避免线段树局限性,所以设置一个新的接口,融合器
            tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
        }
    
        // 获取数组的长度
        public int getSize() { 
            return data.length;
        }
    
        // 获取指定位置的数组值
        public E get(int index) { 
            if(index < 0 || index >= data.length) { 
                throw new IllegalArgumentException("Index is illegal");
            }
            return data[index];
        }
    
        // 返回完全二叉树的数组表示中,一个索引说表示的元素的做孩子节点的索引
        private int leftChild(int index) { 
            return 2 * index + 1;
        }
        // 返回完全二叉树的数组表示中,一个索引所表示的元素的有孩子节点的索引
        private int rightChild(int index) { 
            return 2 * index + 2;
        }
    
        // 返回区间[queryL, queryR]的值
        public E query(int queryL, int queryR) { 
            if(queryL < 0 || queryL >= data.length) { 
                throw new IllegalArgumentException("Index is ilegal.");
            }
            return query(0, 0, data.length - 1, queryL, queryR);
        }
    
        // 在以treeIndex为根的线段树[l...r]的范围里, 搜索区间[queryL...queryR]的值
        private E query(int treeIndex, int l, int r, int queryL, int queryR) { 
            if(l == queryL && r == queryR) { 
                return tree[treeIndex];
            }
    
            // 取中间值
            int mid = l + (r - l) / 2;
            // treeIndex的节点分为[l...mid]和[mid+1...r]两部分
    
             int leftTreeIndex = leftChild(treeIndex);
             int rightTreeIndex = rightChild(treeIndex);
    
             // 如果范围某一侧,直接在那一侧进行查询
             if (queryL >= mid + 1) { 
                 return query(rightTreeIndex, mid + 1, r, queryL, queryR);
             } else if (queryR <= mid) { 
                 return query(leftTreeIndex, l, mid, queryL, queryR);
             }
    
             // 如果范围分布在树的两侧,在两侧分别进行查询
             // 对左孩子,右孩子进行查询
             E leftResult = query(leftTreeIndex, l, mid, queryL, mid);
             E rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);
             // 合并左右查询结果
            return merger.merge(leftResult, rightResult);
        }
    
        // 将index位置的值, 更新为e
        public void update(int index, E e) { 
            if(index < 0 || index >= data.length) { 
                throw new IllegalArgumentException("Index is illegal");
            }
            data[index]  = e;
            update(0, 0, data.length - 1, index, e);
        }
    
        private void update(int treeIndex, int l, int r, int index, E e) { 
            if( l == r) { 
                tree[treeIndex] = e;
                return;
            }
            int mid = l + (r - l) / 2;
            // treeIndex的节点分为[l...mid]和[mid+1...r]两部分
            int leftTreeIndex = leftChild(treeIndex);
            int rightTreeIndex = rightChild(treeIndex);
            if(index >= mid + 1)
                update(rightTreeIndex, mid + 1, r, index, e);
            else // index <= mid
                update(leftTreeIndex, l, mid, index, e);
    
            tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
        }
    
        @Override
        public String toString() { 
            StringBuilder res = new StringBuilder();
            res.append('[');
            for(int i = 0 ; i < tree.length ; i ++){ 
                if(tree[i] != null)
                    res.append(tree[i]);
                else
                    res.append("null");
    
                if(i != tree.length - 1)
                    res.append(", ");
            }
            res.append(']');
            return res.toString();
        }
    }