house_cat

ACM

JAVA(5) 其他(3) 文(1) 算法导论(2) 计算机图形学(4) 面试(2) 题解(2)

/ 注册

全部文章 / ACM （共1篇）

[学习笔记]ST表

给狂妄自负以适当的绝望，这就是真理基本概念 RMQ问题：给定一个长度为N的区间，M个询问，每次询问Li到Ri这段区间元素的最大值/最小值。如果暴力找最大值，复杂度是\(o(n)\)。但如果查询多次，这个复杂度就很大了。解决这个问题的方法是离线ST表和支持在线修改的线段树。 ...

学习笔记 ST表

2018-09-02

0 421