本文共 1894 字，大约阅读时间需要 6 分钟。

1. 题目

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。

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

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/range-sum-query-mutable

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：

2.1 常规前缀和

class NumArray {
   	int *sum = NULL;	int n;public:    NumArray(vector
   
    & nums) {
       	if(nums.empty())    		return;    	n = nums.size();    	sum = new int [n];    	sum[0] = nums[0];        for(int i = 1; i < nums.size(); ++i)        	sum[i] = sum[i-1]+nums[i];    }        void update(int i, int val) {
       	if(!sum)    		return;    	int differ;    	if(i == 0)    		differ = val-sum[i];    	else    		differ = val-(sum[i]-sum[i-1]);        for(int k = i; k < n; ++k)        	sum[k] += differ;    }        int sumRange(int i, int j) {
       	if(!sum)    		return 0;        if(i != 0)        	return sum[j]-sum[i-1];        return sum[j];    }};
   

236 ms 18.9 MB

2.2 树状数组

• 参考：，降低更新复杂度为 $\log n$

class NumArray {
       vector
   
     v;    vector
    
      copy;    int N;public:    NumArray(vector
     
      & nums) {
           N = nums.size();        v.resize(N+1,0);//树状数组要求下标从1开始        copy.resize(N+1,0);        for(int i = 0; i < N; ++i)            update(i,nums[i]);    }        void update(int i, int val) {
           int delta = val-copy[i+1];        copy[i+1] += delta;        i++;        for( ;i <= N; i+= lowbit(i))            v[i] += delta;    }        int sumRange(int i, int j) {
           return getsum(j)-getsum(i-1);    }    int getsum(int i)    {
           int ans = 0;        i++;        for(; i > 0; i-= lowbit(i))            ans += v[i];        return ans;    }    //树状数组    int lowbit(int m)    {
           return m&(-m);    }};
     
    
   

60 ms 18.8 MB

转载地址：https://michael.blog.csdn.net/article/details/105632022 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！