狗家昂赛

lhh_NJU 发表于 2019-6-28 02:46
求问308要求的是binary indexed tree解法吗？感觉太难了吧

这道题pre-preocess一下，用个addition matrix记个sum matrix然后去query就完了。为什么要用tree？能详细说下嘛请问？

求问楼主behavior question大概问了些什么 有什么经验可以分享一下吗？
谢谢！

cleozhang 发表于 2019-7-6 03:09
这道题pre-preocess一下，用个addition matrix记个sum matrix然后去query就完了。为什么要用tree？能详细 ...

pre-process的方法不适用于频繁update的情况。
考虑简化版的一维range sum query：
pre-process的方法：update的复杂度可以到O(n), query的复杂度是O(1)
BIT的方法：update和query的复杂度都是O(logN)

当然我觉得如果follow up没问到，也没必要上BIT...

xzqingzi 发表于 2019/07/11 08:19:44
求问楼主behavior question大概问了些什么 有什么经验可以分享一下吗？
谢谢！

想不全了 大概有 冲突解决、你不喜欢做什么、cross-team 合作什么的