Articles
28
Tags
55
Categories
25
Home
Archives
Tags
Categories
About
Alex's Warm Home
线段树详解
Home
Archives
Tags
Categories
About
线段树详解
Created
2022-02-20
|
Updated
2025-05-12
|
IT
Algorithm
Data Structure
|
Word Count:
70k
|
Reading Time:
3:54mins
|
Post Views:
Input password Here.
Author:
Alex Hu
Link:
https://www.alexhu.one/IT/Data-Structure/线段树详解_2022_02-20_19_14_45/
Copyright Notice:
All articles on this blog are licensed under
CC BY-NC-SA 4.0
unless otherwise stated.
segment_tree
range
Previous
数组里的二叉树
用数组实现的二叉树的性质 二叉树 (其实二叉堆也是) 经常可以用数组实现， 但是有些操作可能不够直观需要特别留意 以下假设数组为 0 索引 数组长度 设 l 为数组长度，h 为二叉树高度，则 父子关系 设父节点为 f, 左右子节点为 cl 和 cr. 则 cl 一定为奇数而 cr 一定为偶数.
Next
树状数组
树状数组详解 简介 树状数组，顾名思义，就是像树一样组织的数组. 它的大体样子如下 (数组元素用 a 表示，树节点用 c 表示): 如图所示， 所谓树状数组就是在数组基础上加上一个向右倾斜的树结构维护一定的数组区间信息. 从图上可以看出， 管理 , 管理 , 管理 , 则管理全部 8 个数. 对于没有在图上显示的也是一样的. c 与 a 的对应关系 10 进制下 c 和 a 的下标关系很难看出来，但是在 2 进制下: 其规律就是节点维护数组 a 中 (x - lowbit (x), x] 的和 而 lowbit (x) 就是 x & -x 即 x 只保留最低位的 1 的值. lowbit (x) 不仅代表所反应的区间长度，同时也是在树上的节点高度 构建 由于树状数组顶层节点的值由多个底层节点的值决定， 因此可以先确定底层节点的值再计算顶层的. 运行复杂度为 O (n) // C++ Version// O(n)建树void init() { for (int i = 1; i <= n; ++i) { t[i] += a[i]; int...
Comments
Gitalk
Valine
Alex Hu
这里是Alex Hu用来记录生活的温馨小窝, 希望他能在这里感到平静与幸福.
Articles
28
Tags
55
Categories
25
Follow Me
Announcement
暂时还没有什么要写的
Contents
1.
线段树的二三事
1.1.
线段树有什么用？
1.2.
线段树长什么样
1.3.
线段树怎么建
1.4.
如何实现区间修改， 以及用懒标记优化它
1.5.
如何实现区间查询
1.6.
一些小 tips
1.7.
引用
Recent Posts
让 Seagate 等厂商的移动硬盘在 Linux 下正确输出 SMART 信息。
2025-05-12
树状数组
2025-05-12
Install and Configure KVM in ArchLinux
2025-05-12
词语翻译问题
2025-05-12
线段树详解
2025-05-12
簡
