求助，长度为 n 的序列的线段树结点个数为什么是 2n-1 啊

一扶苏一 @ 2021-06-16 21:26:19

by Ctjer @ 2021-06-16 21:29:36

x     1   2   3   4   ...

f(x)  1   3   5   7   ...

by _Emiria_ @ 2021-06-16 21:30:35

by Ctjer @ 2021-06-16 21:30:59

线段树就是二叉树吧

by Stinger @ 2021-06-16 21:31:48

@蒟蒻且网抑fks n 不一定是 2 的整数冥啊

by SIGSEGV @ 2021-06-16 21:33:29

若结论对n,n-1成立，则2n个结点的线段树结点数为f(2n)=2f(n)+1=2(2n-1)+1=4n-1，2n-1个线段树的结点为f(2n-1)=f(n)+f(n-1)+1=(2n-1)+(2n-3)+1=4n-3=2(2n-1)+1

瞎胡的归纳法

by Ctjer @ 2021-06-16 21:33:33

线段树里只有度为0和2的点

度为0的也就是叶子节点，有n个

度为2的不就是n-1个了吗……

by koishi_offical @ 2021-06-16 21:33:58

难道2n-1的不是后缀自动机？

by rui_er @ 2021-06-16 21:34:50

考虑如果 n=2^k 线段树是满二叉树，节点数为 \sum\limits_{i=0}^k2^i=2^{k+1}-1=2n-1，在此基础上每去掉一个数就会把父亲、左儿子、右儿子三个节点的父亲和一个儿子去掉，依然符合这个规律？

不知道说的对不对，画了画貌似是对的。

by SIGSEGV @ 2021-06-16 21:35:09

是长度为2n的和长度为2n-1的

打错字了（

by zhy12138 @ 2021-06-16 21:35:11

大概是从叶节点开始，每合并两个点，总点数就少一

所以这个2n-1应该是适用于除叶子以外都有两个儿子的二叉树