I assume you already know the basic concept of BIT, and its two operations: `getSum`

and `update`

. I use a set `bloomed`

to record the index of bloomed flowers, and update the binary index tree. Then everyday I check if the kth flower on the right hand side and on the left hand side has bloomed, and there is no flower between them has bloomed: `getSum(index) == getSum(index - k - 1) or getSum(index) == getSum(index + k + 1) - 1`

. One thing need to notice is that if you check before updating the tree, you need to have that `- 1`

when checking the right hand side.

```
class BITree(object):
def __init__(self, n):
self.node = [0 for _ in range(n + 1)]
def getSum(self, index):
index += 1
result = 0
while index > 0:
result += self.node[index]
index -= index & -index
return result
def update(self, index, d):
index += 1
while index < len(self.node):
self.node[index] += d
index += index & -index
class Solution(object):
def kEmptySlots(self, flowers, k):
"""
:type flowers: List[int]
:type k: int
:rtype: int
"""
bitree = BITree(len(flowers))
bloomed = set()
for day, index in enumerate(flowers):
index -= 1
if index - k - 1 in bloomed and bitree.getSum(index) == bitree.getSum(index - k - 1):
return day + 1
elif index + k + 1 in bloomed and bitree.getSum(index) + 1 == bitree.getSum(index + k + 1):
return day + 1
else:
bloomed.add(index)
bitree.update(index, 1)
return -1
```