分类: data structure | 没什么看头的地方

这里可能没有你想看的...

文章分类

lab 27 paperReading 13 c++ 25 note 5 what happened 1 编程思想 1 linux 1 operating system 2 data structure 3 Computer Network 2 unreal 9 lua 1 leetcode 10 Graphics 2 life 1 💩 1 algorithm 1 interview 1 hands-on 1

                            
                            线段树
                        
                                线段树是一种能够在 \(O(\log n)\) 的时间复杂度下，动态维护区间信息的数据结构。

树状数组
树状数组虽然也能支持 \(O(\log n)\) 的区间查询，但仅仅是区间求和，对于区间最值问题显得有些无力。
线段树
线段树将每个长
                            
                                2024-08-11
                            
                                    data structure
                                
                            后缀自动机(Suffix Automaton)
                        
                                翻阅网络资料两天后顿悟，遂写下心得。

参考资料

OI Wiki
知乎。并贴心地给出了构建过程的中间形态

性质
关于后缀自动机(SAM)的所有概念，其实网上说的都已经差不多了。个人总结出以下几个关键的性质：

在 SAM 中，能够通
                            
                                2024-08-05
                            
                                    data structure
                                
                            C++
                        
                            树状数组
                        
                                树状数组，也称作二叉索引树(Binary Indexed Tree)或 Fenwick 树。 它可以在 \(O(\log n)\) 的时间复杂度下实现单点修改与区间查询两个操作。

参考自 OI wiki。

无特殊说明，本文所有数组下标均
                            
                                2023-09-05
                            
                                    data structure