Tag: Binary Index Tree

Written by Bilbo

K Empty Slots

Given N flowers. One flower blooms per day. Array flowers[i] gives the flower position (1-based) blooms at i + 1th day. Find the first day where there are k not bloomed flowers between two flowers already bloomed. [Optimal]Two Pointers/Sliding Window Solution Put in another word, we need to find two flowers such that all the […]

Written by Bilbo

Binary Index Tree

Binary Index Tree, also known as Partial Sum Tree, is a array based data structure that is good for getting prefix sum and update the array both in O(logN) time. Binary Index Tree Tutorial 1 Binary Index Tree Tutorial 2 The core idea is that y is x’s parent (y –> x). Unset last bit […]