线段树

[Ir1d]

https://oi-wiki.org/ds/seg/

[ghost]

写的不错！

[ForkKILLET]

作者脑洞好大

[Chen-ZHC]

说几个问题：
1.P3372 第48行那个endl 没加std::
2.为什么getsum的时候遍历左子树时直接是sum=?,为什么不是+=？求大佬回答。

[PythonSimon]

2.-因为之前sum就是0呀，这里sum+=getsum...就等价于sum=getsum...

[ghost]

蒟蒻我很想问个问题：
权值线段树是什么？它是线段树吗？

[H-J-Granger]

线段树的优化。。。
编译器不是傻子。。

[zmxqs]

@bluedone 权值线段树？其实n棵权值线段树组成了一棵主席树。可以查询区间第k小，或者排名之类的

[Early0v0]

@Chen-ZHC
说几个问题：
1.P3372 第48行那个endl 没加std::
2.为什么getsum的时候遍历左子树时直接是sum=?,为什么不是+=？求大佬回答。

sum 的初值是 0，sum+=getsum() 即为 sum=0+getsum()，所以写 = 和 += 都是可以的

[pot-code]

关于区间修改的部分

if (b[p] && s != t) {
	d[p * 2] += b[p] * (m - s + 1), d[p * 2 + 1] += b[p] * (t - m);
	b[p * 2] += b[p], b[p * 2 + 1] += b[p];
	b[p] = 0;
}

这个地方的 s!=t 并不能规避 p 值超出数组大小的问题，而且还不是第一个判断条件，很容易导致错误。这块代码前面应该加上 if (s<t) return 来保护（如果 s==t，那么函数开头的判断就已经考虑到了，再往下执行毫无意义），否则 p 指向最后一层叶子节点时，p*2 就会导致索引超出边界。

其次，在区间赋值的例子中，光靠判断 b[p] 不为 0 是不严谨的，如果赋值的目标值刚好为 0，那么赋值 0 的操作就不会被执行，下推过程完全失效。所以需要添加一个额外的 bool 数组来表示 p 位置是否有懒标记。

[Ir1d]

@pot-code Hi，有没有兴趣开个 PR 订正正文内容（

[thallium]

@bluedone
蒟蒻我很想问个问题：
权值线段树是什么？它是线段树吗？

权值线段树基本上就是统计数字的个数的线段树，他的叶节点是数字的个数而非某个具体的数字。简单应用可以查询整个数组的第k大，可持久化之后可以实现查询区间第k大

[ouuan]

他的叶节点是数字的个数而非某个具体的数字

数字的个数不是具体的数字？

您想表达“不是某个维护的量的值， 而是某个值在维护的这些量中出现的次数”吧。

其实我更喜欢“以数值为下标”这种说法，或者是”对 cnt（一个值的出现次数）数组建线段树“。

[Socrates1232]

对于维护区间大小为n的线段树而言，开2n大小的线段树完全够了。考虑到n可以被分解为完全二叉树部分(大小为2^k-1)和剩余部分(2^k>=r>0)，而一个深度为k + 1的完全二叉树数组即可把这两部分全装下(大小为2^(k+1)-1)。如果我开2n的话，2n=2^(k+1)-2+2r>=2^(k+1)-1

[volmodaoist]

标签永久化的方法能不能用在的带有乘法标记与加法标记的线段树上面呢？

[zx0034]

如果你是要实现区间修改为某一个值而不是加上某一个值的话
这部分update的时候，满足条件if (l <= s && t <= r) 是不是要更新v[p]=1 不然 后面的if(v[p])应该永远命中不了？也就没有办法把状态下推？

[drmsker]

同感，有问题啊这

[Tiikee]

并没有问题，在下一次遍历到节点，发现懒标记时，自动往下更新左右孩子。懒标记的内核就是，用到的时候再往下改。

[Tiikee]

懒标记的区间修改图画错了，[3,5]区间加5以后，根节点变成了75，不是60。

[Tiikee]

还有后面的33是38

[yanzhuoxuan]

所以在python里加 # 如果写成 (s + t) >> 1 可能会超出 int 范围 干吗？

[jiangmuran]

好像没有求最大值？

[DBWGLX]

线段树的深度那里是log2 n向下取整吧：
// 1
// 2 3
// 4 5 6 7
// 8 9
//1 log1==0
//2 log2==1 log3==2//（这里上取整不就不一样了吗，而且求总结点数那里加一了，更对应下去整了
//4 log4==2 log5==log6==log7==3
//8

[DBWGLX]

//完全二叉树的总结点数就是：
//等比数列求和
//1*（2^（层数） - 1）/(2-1)

[Minecraftwhr]

或者叫类st表树？

[Minecraftwhr]

有点像st表啊

[EvilDjango]

学习了！

[HeavenOJ]

建树过程如何保证是完全二叉树？
举个例子，12个数的序列，d1:[1,12] d2[1,6] d3[7,12] d4[1,3] d5[4,6] d6[7,9] d7[10,12] d8[1,2] d9[3,3] d10[4,5]
显然d9是叶子节点，然而 d8有两个子节点，d10也还有两个。显然这不满足完全二叉树的性质。
求助这是怎么回事？

[ayyHA]

这里的C++模板中的maintain函数不是下方lazy标记吗，应该是push_down吧，名字起错了吧

[ayyHA]

下方->下放

[typed-sigterm]

下放不就是在维护吗

[oier03]

写得好！！！