故事背景

我们知道，OIer（YBT） 们往往会先学习树状数组而不是先学习线段树,冲着
就是树状数组比线段树要长亿倍。但是我在参加莆田市2024 \texttt{C++ CSP-S} 专项训练 \texttt{Day-2} 的时候，我们的老师试图在一天之内让我们生吞 二叉树，线段树，树状数组，平衡树 ... 显然是有课后作业 900\space pts 的 \texttt{dalao} 的，但是显然不是我。
所以当我看到课后作业 T-3 的时候，丁真了它可以用树状数组写。后来发现它是线段树的模板题 ( Luogu P3372 )于是我开心地对着YBT写出来一份树状数组，丢到洛谷上一交，AC 了。于是非常开心地交上去，调了好久发现题目不一样。后者是要求区间修改和区间查询。于是我又写了洛谷树状数组的模板题II，这个是用了差分+树状数组，区间修改单点查询。但是还是不行啊，我要的是区间修改和区间查询。使用for循环被卡掉后，破防。然后 \texttt{ZXK} 告诉我这是线段树模板题。
后来，我发现了这篇题解,但是破防。于是水完讲评灰溜溜回家理解线段树。

线段树理解

线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。
线段树可以在 O(\log N) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。 ——OI Wiki-线段树。

显然可以用Excel来理解。

放在图里，他就是中规中矩的二叉树

这样，我们在维护查找每一个区间的时候，就没有必要维护查找到每一个节点，只要维护相应的区间就可以了。
比如说我要找
- \omega_{[1,4]} = \omega_{[1,3]}+\omega_{[4,4]} = D[4]+D[6] = \omega_{[1,5]}-\omega_{[5,5]}=D[1]-D[7].

基础操作

• 查找
• 区间修改
  · 区间加和：比如我要对区间[1,3]进行整体 +3 的操作，我当然可以给 D[2] 操作，但是又不能只给这个区间操作。（废话如果我要查到比如 D[8] 不就寄了吗） 但是如果逐层修改，那么我写线段数干什么 （直接维护数组不香吗 常数说不定还少）。这时 \texttt{Lazy-Mark} 就闪亮登场了。也就是说，对于没有碰到的区间，它根本就懒得动，只是拿着一张纸条记下了它要干什么。然鹅，当 Boss 催它干活时，它才会执行 \texttt{Mark} 的操作。

代码实现

写一半的模板

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
struct Seg{
    ll n;
    ll data[1000010];
    ll get_sum(ll left,ll right){
        ll ans;
        for(ll i=left;i<=right;i++)ans+=data[i];
        return ans;
    }
    struct Cnt{
    //  ll id,Sona,Sonb;
        ll w;
        ll Lazy_Mark;
        ll l,r;
    }cnts[1000010];
    //对于父亲节点p，其两个子节点分别为2p,2p+1

    //-------------------------------------------------------
    //Build
    void init(){
        cnts[1].l=1;
        cnts[1].r=n;
        cnts[1].w=build(1);
    }
    ll build(ll p){//构建P节点的两个子树 (push_up)
        if(cnts[p].l==cnts[p].r){
            return cnts[p].w=data[l];
        }
        ll lp=cnts[p].l,rp=cnts[p].r;
        ll s1=2*p,s2=2*p+1;
        cnts[s1].l=lp,cnts[s1].r=(lp+rp)/2;
        cnts[s2].l=(lp+rp)/2+1,cnts[s2].r=rp;
        return cnts[p].w=build(s1)+build(s2);
    }
    //-------------------------------------------------------





};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    return 0;
}