type
status
date
slug
summary
tags
category
icon
password
本文受到AtCoder官方库和来写一个像stl一样的线段树的启发
线段树
线段树维护的信息在很多时候可以认为是满足(幺)半群的性质的信息
一个幺半群 ,其中 为在集合 上定义的二元运算符,幺半群具有以下性质:
- 封闭性: 和 有
- 结合律: 有
- 存在幺元:即 满足 有 , 为左幺元;或 , 为右幺元
那么我们只需定义,, 就可以实现模版线段树了。
Data 就是定义的 , 就是定义的 , 就是定义的
不过还需要一个 , 和 都需要用到
详细说明待更……
来看一下最简单的线段树问题【模板】线段树 1