leetcode Range Sum Query - Immutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
- You may assume that the array does not change.
- 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
