0%

leetcode Range Sum Query - Mutable

leetcode Range Sum Query - Mutable

Given an integer array nums, find the sum of the elements between indices i and j (ij), 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:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly. 题目地址 : leetcode Range Sum Query - Mutable

题意:

给定一个数组,让你正确实现如下两种操作:

  • update(i , val ):让下标为i增加val
  • sumRange(i,j): 计算数组从i到j的值

 

思路:

其实在 leetcode Range Sum Query – Immutable 我已经给多可变数组的解法。

直接上fenwick tree或者线段树都行。

fenwick tree比较好写,水水的1A~

关于fenwick tree看这里:  Fenwick tree (binary indexed tree)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class NumArray(object):
def __init__(self, nums):
"""
initialize your data structure here.
:type nums: List[int]
"""
self.sum_array = [0] * (len(nums) + 1)
self.nums = nums
self.n = len(nums)
for i in xrange(len(nums)):
self.add(i + 1,nums[i])

def add(self,x,val):
while x <= self.n:
self.sum_array[x] += val
x += self.lowbit(x)

def lowbit(self,x):
return x & -x

def sum(self,x):
res = 0
while x >0:
res += self.sum_array[x]
x -= self.lowbit(x)
return res

def update(self, i, val):
"""
:type i: int
:type val: int
:rtype: int
"""
self.add(i + 1, val - self.nums[i])
self.nums[i] = val

def sumRange(self, i, j):
"""
sum of elements nums[i..j], inclusive.
:type i: int
:type j: int
:rtype: int
"""
if not self.nums: return 0
return self.sum(j+1) - self.sum(i)


请我喝杯咖啡吧~