[Swift]LeetCode307. 区域和检索 - 数组可修改 | Range Sum Quer

 1 class NumArray {
 2 
 3     var tree : [Int]
 4     var size : Int
 5    
 6     
 7     init(_ nums: [Int]) {
 8         size = nums.count
 9         tree = Array(repeating: 0,count: size << 2)
10         
11         if size != 0 {
12             build(1,size,1,nums)
13         }
14         
15     }
16     
17     func build(_ l :Int,_ r : Int,_ rt : Int,_ nums : [Int]){
18         if l == r {
19             tree[rt] = nums[l-1]
20             return
21         }
22         
23         let m = (l + r) >> 1
24         build(l,m,rt<<1,nums)
25         build(m+1,r,rt<<1|1,nums)
26         pushup(rt)
27     }
28     
29     func pushup(_ rt : Int) {
30         tree[rt] = tree[rt<<1] + tree[rt << 1|1]
31     }
32     
33     func update(_ p : Int,_ val : Int,_ l : Int,_ rt : Int){
34         if l == r {
35             tree[rt] = val
36             return
37         }
38         
39         let m = (l + r) >> 1
40         if p <= m {
41             update(p,val,l,rt << 1)
42         }else {
43             update(p,m+1,rt << 1 | 1)
44         }
45         
46         pushup(rt)
47     }
48     
49     func query(_ L : Int,_ R : Int,_ rt : Int) -> Int {
50         if L <= l && r <= R {
51             return tree[rt]
52         }
53         
54         let m = (l + r) >> 1
55         var ans = 0
56         if L <= m {
57             ans += query(L,R,rt<<1)
58         }
59         if R >= m+1 {
60             ans += query(L,rt << 1|1)
61         }
62         
63         return ans
64     }
65     
66     func update(_ i: Int,_ val: Int) {
67         update(i+1,1,1)
68 
69         
70     }
71     
72     func sumRange(_ i: Int,_ j: Int) -> Int {
73         return query(i+1,j+1,1)
74     }
75 }
76 
77 /**
78  * Your NumArray object will be instantiated and called as such:
79  * let obj = NumArray(nums)
80  * obj.update(i,val)
81  * let ret_2: Int = obj.sumRange(i,j)
82  */

 1 class NumArray {
 2 
 3  var _nums : [Int]
 4     var sums : [Int]
 5     var changes : [Int : Int]
 6     
 7     init(_ nums: [Int]) {
 8         _nums = nums
 9         sums = nums
10         changes = [Int : Int]()
11         
12         if nums.isEmpty {
13             return
14         }
15         
16         for i in 1..<nums.count {
17             sums[i] += sums[i-1]
18         }
19         
20     }
21     
22     func update(_ i: Int,_ val: Int) {
23         if i >= _nums.count {
24             return
25         }
26         let c = val - _nums[i]
27         _nums[i] = val
28         if changes[i] != nil {
29             changes[i]! += c
30         }else {
31             changes[i] = c
32         }
33         
34         if !_nums.isEmpty && changes.count > _nums.count / 2 {
35             sums = _nums
36             for i in 1..<_nums.count {
37                 sums[i] += sums[i-1]
38             }
39             changes.removeAll()
40         }
41 
42         
43     }
44     
45     func sumRange(_ i: Int,_ j: Int) -> Int {
46         var res = sums[j]
47         if i > 0 {
48             res -= sums[i-1]
49         }
50         for dic in changes {
51             if dic.key <= j && dic.key >= i {
52                 res += dic.value
53             }
54         }
55         return res
56     }
57 }
58 
59 /**
60  * Your NumArray object will be instantiated and called as such:
61  * let obj = NumArray(nums)
62  * obj.update(i,val)
63  * let ret_2: Int = obj.sumRange(i,j)
64  */
65  

 1 class NumArray {
 2     
 3     private var sums: [Int] = []
 4     private var nums: [Int] = []
 5 
 6     init(_ nums: [Int]) {
 7         guard !nums.isEmpty else {
 8             return
 9         }
10         
11         var sums = Array(repeating: 0,count: nums.count)
12         sums[0] = nums[0]
13         for index in 1..<nums.count {
14             let num = nums[index]
15             sums[index] = sums[index - 1] + num
16         }
17 
18         self.sums = sums
19         self.nums = nums
20     }
21     
22     func update(_ i: Int,_ val: Int) {
23         guard i < nums.count else {
24             return
25         }
26         
27         let offset = val - nums[i]
28         guard offset != 0 else {
29             return
30         }
31         
32         for index in i..<nums.count {
33             sums[index] += offset
34         }
35         
36         nums[i] = val
37     }
38     
39     func sumRange(_ i: Int,_ j: Int) -> Int {
40         if i == 0 {
41             return sums[j]
42         } else {
43             return sums[j] - sums[i - 1]
44         }
45     }
46 }
47 
48 /**
49  * Your NumArray object will be instantiated and called as such:
50  * let obj = NumArray(nums)
51  * obj.update(i,val)
52  * let ret_2: Int = obj.sumRange(i,j)
53  */

 1 class NumArray {
 2 
 3     var nums: [Int]
 4     var sumArray = [Int]()
 5     
 6     init(_ nums: [Int]) {
 7         self.nums = nums
 8         sumArray = nums
 9         if nums.count > 1 {
10             for i in 1 ..< nums.count {
11                 sumArray[i] = sumArray[i - 1] + nums[i]
12             }
13         }
14     }
15     
16     func update(_ i: Int,_ val: Int) {
17         let diff = val - nums[i]
18         self.nums[i] = val
19         for j in i ..< nums.count {
20             sumArray[j] += diff
21         }
22     }
23     
24     func sumRange(_ i: Int,_ j: Int) -> Int {
25         if i == 0 {
26             return sumArray[j]
27         } else {
28             return sumArray[j] - sumArray[i - 1]    
29         }
30         
31     }
32 }
33 
34 /**
35  * Your NumArray object will be instantiated and called as such:
36  * let obj = NumArray(nums)
37  * obj.update(i,val)
38  * let ret_2: Int = obj.sumRange(i,j)
39  */
40