大佬用的线段树刷题的实例：https://leetcode-cn.com/submissions/detail/300962892/

[LCP 52. 二叉搜索树染色](https://timpcfan.notion.site/LCP-52-6df3aa029d8d45c2b16da8c2dd4bb834)

class Solution:
    def numTeams(self, rating: List[int]) -> int:

        '''线段树模板'''
        def add(i, delta):          # 坐标i处依次添加delta
            i += len(tree)//2       # 转换到线段树下标
            while i > 0:
                tree[i] += delta
                i //= 2
        
        def query(i, j):            # 区域和检索 range sum
            i += len(tree) // 2     # 转换到线段树下标
            j += len(tree) // 2
            summ = 0
            while i <= j:
                if i % 2 == 1:      # i为右子树
                    summ += tree[i]
                    i += 1
                if j % 2 == 0:      # i为左子树
                    summ += tree[j]
                    j -= 1
                i //= 2
                j //= 2
            return summ

        '''主程序'''
        # 离散化：绝对数值转秩次rank
        uniques = sorted(rating)        # rating没有重复值
        rank_map = {v:i for i,v in enumerate(uniques)}    #【注意：rank从0开始】
        # print(rank_map)

        # 构建线段树
        tree = [0] * (len(rank_map) * 2)

        # 枚举中间点
        ans = 0
        n = len(rating)
        add(rank_map[rating[0]], 1)     # 先将第一个元素入列
        for i in range(1, n-1):         # 从第二个元素开始遍历，直至倒数第二个元素
            rank = rank_map[rating[i]]  # 当前元素的排名/秩次

            small1 = query(0, rank-1)   # 查询前序元素中排名<rank的元素数目
            large1 = i - small1         # small1 + large1 = i

            small2 = rank - small1      # small1 + small2 = rank
            large2 = n-1 - i - small2   # small2 + large2 = n-1-i

            add(rank, 1)                # 当前元素入列

            ans += small1*large2 + large1*small2
        
        return ans

作者：flix
链接：<https://leetcode.cn/problems/count-number-of-teams/solution/by-flix-3lu9/>
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

算法学习笔记(76): zkw线段树

线段树｜SegmentTree

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。

线段树可以在 $O(\log N)$ 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

线段树维护的信息在很多时候可以认为是满足（幺）半群的性质的信息。

一个幺半群 $M=(S,\circ ,e)$，其中 $\circ$ 为在集合 $S$ 上定义的二元运算符，幺半群具有以下性质：

封闭性：$\forall x\in S$ 和 $\forall y\in S$ 有 $x\circ y\in S$。
结合律：$\forall x,y,z\in S$ 有 $(x\circ y)\circ z=x\circ (y\circ z)$。
存在幺元：即 $\exists e\in S$ 满足 $\forall x \in S$ 有 $e\circ x=x$，$e$ 为左幺元；或 $x\circ e=x$，$e$ 为右幺元。

我们观察到线段树上的信息一般满足这样的性质，一些数域上的加法与乘法自然，考虑二元的 $\max(x,y)$ 运算，此时幺元为 $-\infty$ 也满足这样的性质（一般左右幺元相同时简称为幺元）。

线段树

线段树的基本结构与建树

线段树将每个长度不为 1 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。

有个大小为 5 的数组 $a=\{10,11,12,13,14\}$，要将其转化为线段树，有以下做法：设线段树的根节点编号为 1，用数组 d 来保存我们的线段树，d_i 用来保存线段树上编号为 i 的节点的值（这里每个节点所维护的值就是这个节点所表示的区间总和）。