Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitee38a5a

Browse files
author
Vladimir Zamyatin
committed
Fix a bug in SegmentTree
1 parent6cc7c2f commitee38a5a

File tree

2 files changed

+28
-28
lines changed

2 files changed

+28
-28
lines changed

‎Segment Tree/SegmentTree.playground/Contents.swift‎

Lines changed: 23 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@ public class SegmentTree<T> {
2828
self.init(array: array, leftBound:0, rightBound: array.count-1, function: function)
2929
}
3030

31-
publicfunc query(withLeftBound:Int, rightBound:Int)->T{
31+
publicfunc query(leftBound:Int, rightBound:Int)->T{
3232
ifself.leftBound== leftBound &&self.rightBound== rightBound{
3333
returnself.value
3434
}
@@ -37,12 +37,12 @@ public class SegmentTree<T> {
3737
guardlet rightChild= rightChildelse{fatalError("rightChild should not be nil")}
3838

3939
if leftChild.rightBound< leftBound{
40-
return rightChild.query(withLeftBound: leftBound, rightBound: rightBound)
40+
return rightChild.query(leftBound: leftBound, rightBound: rightBound)
4141
}elseif rightChild.leftBound> rightBound{
42-
return leftChild.query(withLeftBound: leftBound, rightBound: rightBound)
42+
return leftChild.query(leftBound: leftBound, rightBound: rightBound)
4343
}else{
44-
letleftResult= leftChild.query(withLeftBound: leftBound, rightBound: leftChild.rightBound)
45-
letrightResult= rightChild.query(withLeftBound:rightChild.leftBound, rightBound: rightBound)
44+
letleftResult= leftChild.query(leftBound: leftBound, rightBound: leftChild.rightBound)
45+
letrightResult= rightChild.query(leftBound:rightChild.leftBound, rightBound: rightBound)
4646
returnfunction(leftResult, rightResult)
4747
}
4848
}
@@ -68,14 +68,14 @@ let array = [1, 2, 3, 4]
6868

6969
letsumSegmentTree=SegmentTree(array: array, function:+)
7070

71-
print(sumSegmentTree.query(withLeftBound:0, rightBound:3)) // 1 + 2 + 3 + 4 = 10
72-
print(sumSegmentTree.query(withLeftBound:1, rightBound:2)) // 2 + 3 = 5
73-
print(sumSegmentTree.query(withLeftBound:0, rightBound:0)) // 1 = 1
71+
print(sumSegmentTree.query(leftBound:0, rightBound:3)) // 1 + 2 + 3 + 4 = 10
72+
print(sumSegmentTree.query(leftBound:1, rightBound:2)) // 2 + 3 = 5
73+
print(sumSegmentTree.query(leftBound:0, rightBound:0)) // 1 = 1
7474

7575
sumSegmentTree.replaceItem(at:0, withItem:2) //our array now is [2, 2, 3, 4]
7676

77-
print(sumSegmentTree.query(withLeftBound:0, rightBound:0)) // 2 = 2
78-
print(sumSegmentTree.query(withLeftBound:0, rightBound:1)) // 2 + 2 = 4
77+
print(sumSegmentTree.query(leftBound:0, rightBound:0)) // 2 = 2
78+
print(sumSegmentTree.query(leftBound:0, rightBound:1)) // 2 + 2 = 4
7979

8080

8181
//you can use any associative function (i.e (a+b)+c == a+(b+c)) as function for segment tree
@@ -96,38 +96,38 @@ let gcdArray = [2, 4, 6, 3, 5]
9696

9797
letgcdSegmentTree=SegmentTree(array: gcdArray, function: gcd)
9898

99-
print(gcdSegmentTree.query(withLeftBound:0, rightBound:1)) // gcd(2, 4) = 2
100-
print(gcdSegmentTree.query(withLeftBound:2, rightBound:3)) // gcd(6, 3) = 3
101-
print(gcdSegmentTree.query(withLeftBound:1, rightBound:3)) // gcd(4, 6, 3) = 1
102-
print(gcdSegmentTree.query(withLeftBound:0, rightBound:4)) // gcd(2, 4, 6, 3, 5) = 1
99+
print(gcdSegmentTree.query(leftBound:0, rightBound:1)) // gcd(2, 4) = 2
100+
print(gcdSegmentTree.query(leftBound:2, rightBound:3)) // gcd(6, 3) = 3
101+
print(gcdSegmentTree.query(leftBound:1, rightBound:3)) // gcd(4, 6, 3) = 1
102+
print(gcdSegmentTree.query(leftBound:0, rightBound:4)) // gcd(2, 4, 6, 3, 5) = 1
103103

104104
gcdSegmentTree.replaceItem(at:3, withItem:10) //gcdArray now is [2, 4, 6, 10, 5]
105105

106-
print(gcdSegmentTree.query(withLeftBound:3, rightBound:4)) // gcd(10, 5) = 5
106+
print(gcdSegmentTree.query(leftBound:3, rightBound:4)) // gcd(10, 5) = 5
107107

108108

109109
//example of segment tree which finds minimum on given range
110110
letminArray=[2,4,1,5,3]
111111

112112
letminSegmentTree=SegmentTree(array: minArray, function: min)
113113

114-
print(minSegmentTree.query(withLeftBound:0, rightBound:4)) // min(2, 4, 1, 5, 3) = 1
115-
print(minSegmentTree.query(withLeftBound:0, rightBound:1)) // min(2, 4) = 2
114+
print(minSegmentTree.query(leftBound:0, rightBound:4)) // min(2, 4, 1, 5, 3) = 1
115+
print(minSegmentTree.query(leftBound:0, rightBound:1)) // min(2, 4) = 2
116116

117117
minSegmentTree.replaceItem(at:2, withItem:10) // minArray now is [2, 4, 10, 5, 3]
118118

119-
print(minSegmentTree.query(withLeftBound:0, rightBound:4)) // min(2, 4, 10, 5, 3) = 2
119+
print(minSegmentTree.query(leftBound:0, rightBound:4)) // min(2, 4, 10, 5, 3) = 2
120120

121121

122122
//type of elements in array can be any type which has some associative function
123123
letstringArray=["a","b","c","A","B","C"]
124124

125125
letstringSegmentTree=SegmentTree(array: stringArray, function:+)
126126

127-
print(stringSegmentTree.query(withLeftBound:0, rightBound:1)) // "a"+"b" = "ab"
128-
print(stringSegmentTree.query(withLeftBound:2, rightBound:3)) // "c"+"A" = "cA"
129-
print(stringSegmentTree.query(withLeftBound:1, rightBound:3)) // "b"+"c"+"A" = "bcA"
130-
print(stringSegmentTree.query(withLeftBound:0, rightBound:5)) // "a"+"b"+"c"+"A"+"B"+"C" = "abcABC"
127+
print(stringSegmentTree.query(leftBound:0, rightBound:1)) // "a"+"b" = "ab"
128+
print(stringSegmentTree.query(leftBound:2, rightBound:3)) // "c"+"A" = "cA"
129+
print(stringSegmentTree.query(leftBound:1, rightBound:3)) // "b"+"c"+"A" = "bcA"
130+
print(stringSegmentTree.query(leftBound:0, rightBound:5)) // "a"+"b"+"c"+"A"+"B"+"C" = "abcABC"
131131

132132
stringSegmentTree.replaceItem(at:0, withItem:"I")
133133
stringSegmentTree.replaceItem(at:1, withItem:" like")
@@ -136,4 +136,4 @@ stringSegmentTree.replaceItem(at: 3, withItem: " and")
136136
stringSegmentTree.replaceItem(at:4, withItem:" swift")
137137
stringSegmentTree.replaceItem(at:5, withItem:"!")
138138

139-
print(stringSegmentTree.query(withLeftBound:0, rightBound:5))
139+
print(stringSegmentTree.query(leftBound:0, rightBound:5))

‎Segment Tree/SegmentTree.swift‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,7 @@ public class SegmentTree<T> {
3535
self.init(array: array, leftBound:0, rightBound: array.count-1, function: function)
3636
}
3737

38-
publicfunc query(withLeftBound:Int, rightBound:Int)->T{
38+
publicfunc query(leftBound:Int, rightBound:Int)->T{
3939
ifself.leftBound== leftBound &&self.rightBound== rightBound{
4040
returnself.value
4141
}
@@ -44,12 +44,12 @@ public class SegmentTree<T> {
4444
guardlet rightChild= rightChildelse{fatalError("rightChild should not be nil")}
4545

4646
if leftChild.rightBound< leftBound{
47-
return rightChild.query(withLeftBound: leftBound, rightBound: rightBound)
47+
return rightChild.query(leftBound: leftBound, rightBound: rightBound)
4848
}elseif rightChild.leftBound> rightBound{
49-
return leftChild.query(withLeftBound: leftBound, rightBound: rightBound)
49+
return leftChild.query(leftBound: leftBound, rightBound: rightBound)
5050
}else{
51-
letleftResult= leftChild.query(withLeftBound: leftBound, rightBound: leftChild.rightBound)
52-
letrightResult= rightChild.query(withLeftBound:rightChild.leftBound, rightBound: rightBound)
51+
letleftResult= leftChild.query(leftBound: leftBound, rightBound: leftChild.rightBound)
52+
letrightResult= rightChild.query(leftBound:rightChild.leftBound, rightBound: rightBound)
5353
returnfunction(leftResult, rightResult)
5454
}
5555
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp