## Tuesday, August 9, 2016

isToggled(long idx)
toggle(long start, long end)

[Solution]
[Solution #1]
Merge Interval

Query的时候就看idx是不是在list里面。
Pros: Query time O(k), where k is the number of toggled bubbles.
Cons: A little bit hard to implement
[Solution #2]
Bit Manipulation

[Solution #3]
Interval Tree
Interval Tree是一个BST, 每个node是记录一个range [low, high]，BST结构根据low来维护。除了记录range，每个node还记录一个maxValue表示以该结点为root的整个subtree的最大high值。
Insert node的时候不需要像segment tree那样考虑partial overlap的情况，如果不是complete overlap, 都作为一个新的node加入到bst，沿路更新每个node的maxValue就好了。

 `class` `Solution {` `  `  `  ``ITNode root;` `  `  `  ``public` `boolean` `isToggled(``long` `idx) {` `    ``int``[] count = {``0``};` `    ``dfs(root, count, idx);` `    ``return` `count[``0``] % ``2` `!= ``0``;` `  ``}` `  `  `  ``private` `void` `dfs(ITNode root, ``int``[] count, ``long` `idx) {` `    ``if` `(root == ``null``) {` `      ``return``;` `    ``}` `    `  `    ``if` `(root.interval.low <= idx && idx <= root.interval.high) {` `      ``count[``0``]++;` `    ``}` `    ``dfs(root.left, count, idx);` `    ``dfs(root.right, count, idx);` `  ``}` `  `  `  ``public` `void` `toggle(``long` `start, ``long` `end) {` `    ``if` `(root == ``null``) {` `      ``root = ``new` `ITNode(``new` `Interval(start, end));` `    ``}` `    ``else` `{` `      ``insert(root, ``new` `Interval(start, end));` `    ``}` `  ``}` `  `  `  ``private` `ITNode insert(ITNode root, Interval interval) {` `    ``if` `(root == ``null``) {` `      ``return` `new` `ITNode(interval);` `    ``}` `    ``if` `(interval.low < root.interval.low) {` `      ``root.left = insert(root.left, interval);` `    ``}` `    ``else` `{` `      ``root.right = insert(root.right, interval);` `    ``}` `  ``}` `  `  `  ``private` `class` `ITNode {` `    ``Interval interval;` `    `  `    ``ITNode left;` `    ``ITNode right;` `    `  `    ``ITNode(Interval interval) {` `      ``this``.interval = interval;` `    ``} ` `  ``}` `  `  `  ``private` `class` `Interval {` `    ``long` `low;` `    ``long` `high;` `    `  `    ``Interval(``long` `low, ``long` `high) {` `      ``this``.low = low;` `      ``this``.high = high;` `    ``}` `  ``}` `  `  `}`