土法炼钢兴趣小组的算法知识备份

线段树与树状数组：区间问题的优雅武器

2026-04-21 | algorithms | #segment-tree #fenwick-tree #range-query #lazy-propagation #competitive-programming

当你第一次看到 O(log n) 内完成区间求和与区间修改时，很难不为这两棵树的设计之精巧而感到震撼。线段树用递归分治将区间层层拆解，树状数组用二进制索引在数组上翩翩起舞——它们是算法竞赛与工业系统中处理区间问题的两把最优雅的武器。