如果题目变成区间修改、查询(查询数的和,修改是 +k+k+k 不是 →k\to k→k),是否可以使用 O(logn)O(\log n)O(logn) 的复杂度完成每次操作,空间是多少?
我想的一个修改方法是:每次新建节点,当区间包含时新建一个节点,左右儿子分别设置成原先的,然后打上 tag。
如何下放?我的想法是不做修改性的下放,在查询时候加个参数表示当前 tag 的和,然后大概是 log\loglog 的复杂度。
不知道是否正确?