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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139
| type SegmentTree struct { nums []int su []int mx []int mi []int negInf int posInf int }
func NewSegmentTree(nums []int, negInf int, posInf int) *SegmentTree { ans := SegmentTree{ nums: nums, su: make([]int, 4*len(nums)), mx: make([]int, 4*len(nums)), mi: make([]int, 4*len(nums)), negInf: negInf, posInf: posInf, } ans.build(1, 0, len(nums)-1) return &ans }
func (st *SegmentTree) build(idx int, left int, right int) { if left == right { st.su[idx] = st.nums[left] st.mx[idx] = st.nums[left] st.mi[idx] = st.nums[left] return } mid := left + (right-left)/2 st.build(idx*2, left, mid) st.build(idx*2+1, mid+1, right) st.pushUp(idx) } func (st *SegmentTree) pushUp(idx int) { st.su[idx] = st.su[idx*2] + st.su[idx*2+1] st.mx[idx] = max(st.mx[idx*2], st.mx[idx*2+1]) st.mi[idx] = min(st.mi[idx*2], st.mi[idx*2+1]) }
func (st *SegmentTree) add(idx int, left int, right int, delta int, i int) { if left == right { st.su[idx] += delta st.mx[idx] += delta st.mi[idx] += delta return } mid := left + (right-left)/2 if i <= mid { st.add(idx*2, left, mid, delta, i) } else { st.add(idx*2+1, mid+1, right, delta, i) } st.pushUp(idx) } func (st *SegmentTree) Add(i int, delta int) { st.add(1, 0, len(st.nums)-1, delta, i) }
func (st *SegmentTree) update(idx int, left int, right int, val int, i int) { if left == right && i == left { st.su[idx] = val st.mx[idx] = val st.mi[idx] = val return } mid := left + (right-left)/2 if i <= mid { st.update(idx*2, left, mid, val, i) } else { st.update(idx*2+1, mid+1, right, val, i) } st.pushUp(idx) } func (st *SegmentTree) Update(i int, val int) { st.update(1, 0, len(st.nums)-1, val, i) }
func (st *SegmentTree) sum(idx int, left int, right int, L int, R int) int { if left >= L && right <= R { return st.su[idx] } mid := left + (right-left)/2 ans := 0 if L <= mid { ans += st.sum(idx*2, left, mid, L, R) } if R > mid { ans += st.sum(idx*2+1, mid+1, right, L, R) } return ans } func (st *SegmentTree) Sum(L int, R int) int { return st.sum(1, 0, len(st.nums)-1, L, R) }
func (st *SegmentTree) max(idx int, left int, right int, L int, R int) int { if left >= L && right <= R { return st.mx[idx] } mid := left + (right-left)/2 ans := st.negInf if L <= mid { ans = max(ans, st.max(idx*2, left, mid, L, R)) } if R > mid { ans = max(ans, st.max(idx*2+1, mid+1, right, L, R)) } return ans } func (st *SegmentTree) Max(L int, R int) int { return st.max(1, 0, len(st.nums)-1, L, R) }
func (st *SegmentTree) min(idx int, left int, right int, L int, R int) int { if left >= L && right <= R { return st.mi[idx] } mid := left + (right-left)/2 ans := st.posInf if L <= mid { ans = min(ans, st.min(idx*2, left, mid, L, R)) } if R > mid { ans = min(ans, st.min(idx*2+1, mid+1, right, L, R)) } return ans } func (st *SegmentTree) Min(L int, R int) int { return st.min(1, 0, len(st.nums)-1, L, R) }
GO
|