线段树

数据结构里的高达：拼装麻烦，但拼好之后区间问题基本横着走。本合集收录线段树题目，随训练持续补完。

线段树模板（区间修改 + 区间查询 + 懒标记）

用 Python 重写的线段树模板。线段树的记忆点在于写代码时脑子里要有那棵树——自顶向下构建，节点 root 的左右孩子是 2*root 和 2*root+1，懒标记在下探时才向下推。

class segment_tree:
    def __init__(self, nums):
        n = len(nums)
        self.nums = nums
        self.tree = [0] * 4 ...

一文解决逆序数

一道逆序数，四种写法，从面试到竞赛一网打尽。计算逆序数有两种思路：

归并排序：统计归并过程中「右边元素先出列」时跨过的元素数；

值域计数：按 rank 逐个把元素落位计数，当前元素的逆序贡献等于值域区间 $[rank+1, n]$ 上的计数和——需要单点修改 + 区间求和的数据结构。

leetcode 上有一道弱化的模板题，下面四份代码都以它为载体。