leetcode 2038题, segment Tree的模板

[Jintao-Huang]

你好, 正在阅读leetcode-cookbook, 写的很好, 遇到了一些问题

1. 关于2038题 As += Acont - 2 Bs += Bcont - 2 是否应该改成 As += 1 Bs += 1 (虽然这两种情况都是通过的, 但这应该是测试样例少的关系) =========

2. 关于Segment Tree的模板 lazy节点的update, query中出现了for循环, 这好像和我学习的lazy tag不太一样, 是否是写错了 ref: https://oi-wiki.org/ds/seg/#%E5%AE%9E%E7%8E%B0_2 补充: 其中的计数问题那块中, 函数updateCountInTree中涉及区间更新, 没有使用lazy tag, 其复杂度是否会退化到O(n), 可以使用lazy tag优化到O(logn).

[Jintao-Huang]

3. 关于树状数组的模板 其中的初始化函数Init中, 使用到了两个for循环, 这使得其复杂度为O(n^2). 例如更新节点idx=16(从1开始数), 会使得i-lowbit(i)=0. 应该可以降低到O(n)的复杂度. ref: https://oi-wiki.org/ds/fenwick/#%E5%BB%BA%E6%A0%91_1