With explanation, binary index tree solution, O(nlogn)

• 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: