区间子串询问
💡
原文中文，约800字，阅读约需2分钟。
📝
内容提要
文章探讨了离线算法与动态树的结合，提出通过线段树记录不同位置的查询答案，将复杂度优化至 O(nlog2n + mlogn)。重点在于维护 fail 树与动态树的关系，以简化操作过程并提升效率。
🎯
关键要点
- 文章探讨了离线算法与动态树的结合，提出通过线段树记录不同位置的查询答案。
- 复杂度优化至 O(nlog2n + mlogn)，重点在于维护 fail 树与动态树的关系。
- 动态树不需要在后缀自动机插入字符时跟随 SAM 变化，只需在全部插入完后根据 fail 树构建。
- 线段树支持区间加减和区间求和，可以用树状数组替代。
- 动态树的主要作用是压缩 fail 树，维护上次访问的标记，其它信息可从 SAM 中获取。
➡️
