Skip to content

Commit bcf0928

Browse files
halfrosthalfrost
committed
更新模板
1 parent 6b1b758 commit bcf0928

1 file changed

Lines changed: 8 additions & 8 deletions

File tree

‎template/SegmentTree.go‎

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,7 @@ func (st *SegmentTree) buildSegmentTree(treeIndex, left, right int) {
2828
return
2929
}
3030
leftTreeIndex, rightTreeIndex := st.leftChild(treeIndex), st.rightChild(treeIndex)
31-
midTreeIndex := left + (right-left)/2
31+
midTreeIndex := left + (right-left)>>1
3232
st.buildSegmentTree(leftTreeIndex, left, midTreeIndex)
3333
st.buildSegmentTree(rightTreeIndex, midTreeIndex+1, right)
3434
st.tree[treeIndex] = st.merge(st.tree[leftTreeIndex], st.tree[rightTreeIndex])
@@ -57,7 +57,7 @@ func (st *SegmentTree) queryInTree(treeIndex, left, right, queryLeft, queryRight
5757
if left == queryLeft && right == queryRight {
5858
return st.tree[treeIndex]
5959
}
60-
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)/2, st.leftChild(treeIndex), st.rightChild(treeIndex)
60+
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1, st.leftChild(treeIndex), st.rightChild(treeIndex)
6161
if queryLeft >= midTreeIndex+1 {
6262
return st.queryInTree(rightTreeIndex, midTreeIndex+1, right, queryLeft, queryRight)
6363
} else if queryRight <= midTreeIndex {
@@ -78,7 +78,7 @@ func (st *SegmentTree) QueryLazy(left, right int) int {
7878
}
7979

8080
func (st *SegmentTree) queryLazyInTree(treeIndex, left, right, queryLeft, queryRight int) int {
81-
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)/2, st.leftChild(treeIndex), st.rightChild(treeIndex)
81+
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1, st.leftChild(treeIndex), st.rightChild(treeIndex)
8282
if left > queryRight || right < queryLeft { // segment completely outside range
8383
return 0 // represents a null node
8484
}
@@ -123,7 +123,7 @@ func (st *SegmentTree) updateInTree(treeIndex, left, right, index, val int) {
123123
st.tree[treeIndex] = val
124124
return
125125
}
126-
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)/2, st.leftChild(treeIndex), st.rightChild(treeIndex)
126+
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1, st.leftChild(treeIndex), st.rightChild(treeIndex)
127127
if index >= midTreeIndex+1 {
128128
st.updateInTree(rightTreeIndex, midTreeIndex+1, right, index, val)
129129
} else {
@@ -145,7 +145,7 @@ func (st *SegmentTree) UpdateLazy(updateLeft, updateRight, val int) {
145145
}
146146

147147
func (st *SegmentTree) updateLazyInTree(treeIndex, left, right, updateLeft, updateRight, val int) {
148-
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)/2, st.leftChild(treeIndex), st.rightChild(treeIndex)
148+
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1, st.leftChild(treeIndex), st.rightChild(treeIndex)
149149
if st.lazy[treeIndex] != 0 { // this node is lazy
150150
for i := 0; i < right-left+1; i++ {
151151
st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])
@@ -208,7 +208,7 @@ func (st *SegmentCountTree) buildSegmentTree(treeIndex, left, right int) {
208208
return
209209
}
210210
leftTreeIndex, rightTreeIndex := st.leftChild(treeIndex), st.rightChild(treeIndex)
211-
midTreeIndex := left + (right-left)/2
211+
midTreeIndex := left + (right-left)>>1
212212
st.buildSegmentTree(leftTreeIndex, left, midTreeIndex)
213213
st.buildSegmentTree(rightTreeIndex, midTreeIndex+1, right)
214214
st.tree[treeIndex] = st.merge(st.tree[leftTreeIndex], st.tree[rightTreeIndex])
@@ -240,7 +240,7 @@ func (st *SegmentCountTree) queryInTree(treeIndex, left, right, queryLeft, query
240240
if queryLeft <= st.data[left] && queryRight >= st.data[right] || left == right {
241241
return st.tree[treeIndex]
242242
}
243-
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)/2, st.leftChild(treeIndex), st.rightChild(treeIndex)
243+
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1, st.leftChild(treeIndex), st.rightChild(treeIndex)
244244
return st.queryInTree(rightTreeIndex, midTreeIndex+1, right, queryLeft, queryRight) +
245245
st.queryInTree(leftTreeIndex, left, midTreeIndex, queryLeft, queryRight)
246246
}
@@ -261,7 +261,7 @@ func (st *SegmentCountTree) updateCountInTree(treeIndex, left, right, val int) {
261261
if left == right {
262262
return
263263
}
264-
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)/2, st.leftChild(treeIndex), st.rightChild(treeIndex)
264+
midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1, st.leftChild(treeIndex), st.rightChild(treeIndex)
265265
st.updateCountInTree(rightTreeIndex, midTreeIndex+1, right, val)
266266
st.updateCountInTree(leftTreeIndex, left, midTreeIndex, val)
267267
}

0 commit comments

Comments
 (0)