线段树

线段树基础

线段树可以在 $𝑂(log⁡𝑁)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

原理

• oi-wiki
• 线段树入门 - Bilibili 灵神讲解 ，对应题目 2286. 以组为单位订音乐会的门票 ，我的题解

一些问题与解释

1. 线段树的大小

假设数组的大小是 $n$ ，把它们全部放在底层，满足这样的最小的满二叉树的高度是 $\lceil log_{2}{n} \rceil + 1$ （根节点高度是 $1$ ），结点个数是 $2^ {\lceil log_{2}{n} \rceil + 1} - 1$ ，又因为线段树的下标从 $1$ 开始，因此总的空间就是 $2^{\lceil log_{2}{n} \rceil + 1}$ ，即 $2 << (n-1).bit_length()$ 。

几坨莫名其妙的东西

$\lfloor \log_2 n \rfloor = n.bit_length() - 1 = \lceil \log_2 (n+1) \rceil - 1$

$\lceil \log_2 n \rceil = (n-1).bit_length()= \lfloor \log_2 (n-1) \rfloor + 1$ （当 $n > 1$ 时）

$2^{x} => 1 << x => 2 << (x - 1)$

其实可以直接写 $4n$ 。

代码

• Python
• c++

print("Hello Python")

cout << "Hello C++" << endl;