线段树 (segment tree)
【题目】给定一个数组arr,数组可能非常大。在程序运行过程中,你可能要做好几次query和update操作:
query(arr, L, R) 表示计算数组arr中,从下标L到下标R之间的所有数字的和。
update(arr, i, val) 表示要把arr[i]中的数字改成val。
怎样尽可能快地完成一系列query和update的操作?
线段树可以在花费一些额外空间的情况下,把这两个操作的时间复杂度都控制在O(log(n))。这段视频主要和大家分享线段树的原理和代码实现。
Видео 线段树 (segment tree) канала 黄浩杰
query(arr, L, R) 表示计算数组arr中,从下标L到下标R之间的所有数字的和。
update(arr, i, val) 表示要把arr[i]中的数字改成val。
怎样尽可能快地完成一系列query和update的操作?
线段树可以在花费一些额外空间的情况下,把这两个操作的时间复杂度都控制在O(log(n))。这段视频主要和大家分享线段树的原理和代码实现。
Видео 线段树 (segment tree) канала 黄浩杰
Показать
Комментарии отсутствуют
Информация о видео
Другие видео канала
知识库vs数据库 - Wikidata和SparQL简介ENGG1811 - VBA Programming 第3讲2016年COMP9021_Lab2作业讲解ENGG1811 - VBA Programming 第5讲LZW压缩算法1【压缩篇】【Matlab番外篇】怎样用Matlab生成一段音乐用valgrind查看自己的代码内存使用量posix多线程第4讲:false sharingENGG1811 - VBA Programming 第4讲不通过HTML制作简单的个人网站Comp9021 Lab3题目讲解1vim入门教程(第2讲)posix多线程第2讲:往线程中传参数的方法ENGG1811 - VBA Programming 第2讲Processing数组并查集(Disjoint-set union)第3讲MIPS汇编语言小科普【第1讲】AWK文本处理工具入门教程02java练习讲解02RLFM练习讲解Matlab番外篇:用Matlab解数独(下)