求问Two Sigma店面一题如何解？

zyoppy008 发表于 2016-11-30 10:33
太他妈的屌了。我之前一直觉得bit就是线段树一个特例，但是没深想，就是感觉start end有点多余，递归写起 ...

那个slides里的coding也是很老练，虽然竞赛选手style比较重
觉得看过那个Slide以后我就没再觉得Segment tree需要记忆

maihuabu 发表于 2016-8-4 14:16
此题考查augmented data structure。你可以任选balanced binary search tree，每个node保存self和所有child ...

想请教一下, 有几个细节我不太明白:

1. 如果达到log(n)查找, 那"每个node存child nodes 之和" 我觉得并没法做到log(n)查找啊, 因为从root traverse的时候无法确定是往左child还是往右child走吧?
2. 维护BST(暂时不管Balanced)的delete, 是不是也要分三种情况考虑? 这个真的要在面试中去自己写嘛?