今天ZRtes爆零咯，就不在tes里写了引言：以前一直只会用线段树2，线段树也是一直当做工具使用，一切线段树的科技除了线段树分治基本都不会，因此特作此文记之线段树的lazytag与pushdown为了保证时间复杂度，线段树在做区间修改的时候引入了lazytag的概念，目的是为了节省没必要的时

本文导读：本博客主要介绍了线段树的原理和构造的过程，以及一些例题，如果有不足的点，欢迎指出qwq.线段树\((1)_{36}\):什么是线段树？作为一个蒟蒻qwq，看到"线段树"三个字时，你想到了什么？蒟蒻：我知道！不就是"线段+树"吗！......作者：哎呀，你到底在说什么，还是我来解释吧...1.线段树

题意原题链接给定序列\(a\)，要求维护区间加，区间乘，区间查询三种操作sol显然线段树，事实上，这是一道板子题（luoguP3373），但由于蒟蒻实在是太蒻了，并没有打过这道题。区间加如果我们将区间里的每一个元素都插入线段树做一次修改操作，那么一次修改操作的时间复杂度为\(O(n\logn)\)，此时

原题链接题解树上区间修改加单点查询，虽然可以树状数组，但是线段树更通用一点然而线段树通常处理的是点权，可这里是边权，怎么办呢？我们可以把边权转换成点权，由于每个点的子边有若干个，但父边有且只有一个，这样我们就把边权变成边下方点的点权然后区间修改和单点求和的时候把lca的点权

虽然扫描线很简单，但是我发现理解还是有些不清晰，于是决定写一篇。原问题，或者说是例题一个不好暴力东西，暴力模拟不带优化至少O（n^3）也是一个非常经典的线段树例题（因为懒得画图所以下面就直接用网上dalao的题解里面的图片了）首先，因为我们要在线段树上面记录下来每一个起始点和结束点，所

还打算用作TikZ练习文。感觉用TikZ画图很酷炫。下面不分析具体问题，直接对于普遍的lazytag问题解决。可以lazytag的问题见atcoderlibrary。