标签归档：数据结构

2023
02-21

使用线段树求区间和

线段树（Segment Tree）是一种二叉搜索树，与区间树相似，他将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶子节点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为 O(logN)。而未优化的空间复杂度为 2N ，实际应用时一般还要开 4N 的数组以免.... Read More >

2023
02-21

树状数组 —— 一种支持单点修改和区间查找的数据结构

树状数组（英语：Binary Indexed Tree）又称为二元索引树，由 Fenwick 于 1994年发明，故又称为 Fenwick 树，其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和、区间和。它支持在 O(logn) 的时.... Read More >