You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: src/data_structures/sqrt_decomposition.md
+49Lines changed: 49 additions & 0 deletions
Original file line number
Diff line number
Diff line change
@@ -110,6 +110,55 @@ For example, let's say we can do two types of operations on an array: add a give
110
110
111
111
Finally, those two classes of problems can be combined if the task requires doing **both** element updates on an interval and queries on an interval. Both operations can be done with $O(\sqrt{n})$ complexity. This will require two block arrays $b$ and $c$: one to keep track of element updates and another to keep track of answers to the query.
112
112
113
+
```py
114
+
classSqrtDecomp:
115
+
def__init__(self, nums):
116
+
self.nums = nums
117
+
self.width =int(len(nums) **0.5) +1
118
+
self.bn = (len(nums) //self.width) +1# number of blocks
119
+
self.blocks = [0] *self.bn # precomputed sums
120
+
self.lazy = [0] *self.bn # an additional lazy[block] is added when querying individual elements in a block
121
+
for i inrange(len(nums)):
122
+
self.blocks[i //self.width] += nums[i] # add to corresponding block
123
+
124
+
defupdate(self, i, j, diff):
125
+
first = (i //self.width) +1# first fully covered block
126
+
last = (j //self.width) -1# last fully covered block
127
+
if first > last: # doesn't cover any blocks
128
+
for v inrange(i, j +1):
129
+
self.nums[v] += diff
130
+
self.blocks[v //self.width] += diff
131
+
return
132
+
133
+
for b inrange(first, last +1): # blocks in the middle
134
+
self.lazy[b] += diff
135
+
self.blocks[b] += diff *self.width
136
+
for v inrange(i, first *self.width): # individual cells
137
+
self.nums[v] += diff
138
+
self.blocks[first -1] += diff
139
+
for v inrange((last +1) *self.width, j +1):
140
+
self.nums[v] += diff
141
+
self.blocks[last +1] += diff
142
+
143
+
defquery(self, i, j):
144
+
first = (i //self.width) +1# first fully covered block
145
+
last = (j //self.width) -1# last fully covered block
146
+
res =0
147
+
148
+
if first > last: # doesn't cover any blocks
149
+
for v inrange(i, j +1):
150
+
res +=self.nums[v] +self.lazy[v //self.width]
151
+
return res
152
+
153
+
for b inrange(first, last +1): # add value from blocks
154
+
res +=self.blocks[b]
155
+
for v inrange(i, first *self.width): # add value from individual cells
156
+
res +=self.nums[v] +self.lazy[first -1]
157
+
for v inrange((last +1) *self.width, j +1):
158
+
res +=self.nums[v] +self.lazy[last +1]
159
+
return res
160
+
```
161
+
113
162
There exist other problems which can be solved using sqrt decomposition, for example, a problem about maintaining a set of numbers which would allow adding/deleting numbers, checking whether a number belongs to the set and finding $k$-th largest number. To solve it one has to store numbers in increasing order, split into several blocks with $\sqrt{n}$ numbers in each. Every time a number is added/deleted, the blocks have to be rebalanced by moving numbers between beginnings and ends of adjacent blocks.
0 commit comments