Preface

本文采用的线段树模板是 AtCoder 的线段树模板，可以在 AtCoder Library 处下载并使用。这里简单提一下相关的 API，AtCoder 的线段树是通过 push tag 的方式实现的。

AtCoder 区间修改线段树 lazy_segtree<> API

  1. 模板参数填什么

    模板参数 含义
    S 线段树节点维护的信息
    F 线段树节点上的懒标记
    S op(S left, S right) 子节点节点合并到父节点，即 pull_up() 的过程
    S e() 线段树节点初始化
    S mapping(F, S) 把父节点上的懒标记下放到子节点上，即 push_down()
    F compose(F new, F old) 新的懒标记和旧的懒标记结合。
    注意这个参数顺序非常重要！！！先新标记，再旧标记！！
    F id() 标记的初始化

区间加减、区间取 max，单点查询