0%

leetcode Range Sum Query - Immutable

leetcode Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (ij), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1

sumRange(2, 5) -> -1

sumRange(0, 5) -> -3

Note:

  1. You may assume that the array does not change.
  2. There are many calls to sumRange function. 题目地址  leetcode Range Sum Query - Immutable

题意:

给你一个数组,让你求i,j的和

  • 数组不变
  • 有许多次的计算

思路:

直接记录和。。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class NumArray(object):
def __init__(self, nums):
"""
initialize your data structure here.
:type nums: List[int]
"""
n = len(nums)
self.sum = [0] * (n + 1)
for i in xrange(n):
self.sum[i+1] = self.sum[i] + nums[i]

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

 

复习一下fenwick树,支持修改。(本题数组不变)当然也可以线段树。

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

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
class NumArray(object):
def __init__(self, nums):
"""
initialize your data structure here.
:type nums: List[int]
"""
nums = [0] + nums
self.nums = [0] * len(nums)
self.n = len(nums)

for i in xrange(1, self.n):
self.add(i, nums[i])

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

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

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

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


 

更进一步:

leetcode Range Sum Query – Mutable

请我喝杯咖啡吧~