search

halfrost / LeetCode-Go

✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% / LeetCode 题解
https://books.halfrost.com/leetcode
MIT License
32.76k stars 5.68k forks source link

leetcode 2038题, segment Tree的模板 #268

Open Jintao-Huang opened 1 year ago

Jintao-Huang commented 1 year ago

你好, 正在阅读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 commented 1 year ago
  1. 关于树状数组的模板 其中的初始化函数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