题解：P3372 【模板】线段树 1

· · 题解

前言

本篇题解来源于我初学线段树时根据线段树的性质所推导的一种线段树，现在看来应该是 zkw 线段树的一种实现。

其优点在于码量小，常数小，其缺点在于维护区间操作时由于标记永久化的思路而有所限制，并且复杂度可能退化。

何为线段树

线段树是一种基于分治的数据结构，可以维护各种符合结合律的区间上问题。

为了方便理解，展示一棵用满二叉树构建的线段树：

可以发现，线段树的每一个子节点都维护了其两个子节点的和。这样，我们要对某个区间中的所有数进行相加时：

只需要查询到对应的区间上覆盖的节点，并且将其贡献累加到统领其的节点上就可以了。但是怎么查询某个区间的和呢？

不难发现，我们所遇到的困难，在于我们刚才所查询到的子节点并没有被刚才的操作所更新。但是，我们所查询到的子节点所需要的操作，一定是被我们刚才所做的操作完全覆盖的。

因此，我们在做区间加的时候，可以留存一个“懒标记”lazy，表示这一整个区间都需要进行此加法。作查询时，从子节点向上把其所需要进行的加法“扯下来”即可。

注意该加法的贡献需要乘以子区间自身的长度。

关于跳点

我们可以直接将线段树建成一颗满二叉树，这样，所有的节点的亲子节点都可以通过位运算的方式取得。

对于“一个区间所对应的哪些节点”，可以采用类似树状数组的 lowbit 操作取得。但是，需要额外判断：不能跳出右区间的范围。

解法

有了以上数据结构，我们直接依据题意模拟就可以啦。

AC Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define min_unlocked(_x,_y) ((_x)<(_y)?(_x):(_y))

const int N=5e5+9,M=1<<__lg(N)+1,K=M<<1; //整个原数组都偏移了 M 个位置，到达了树的叶子节点上
int n,m,v[K],lazy[K];

void add(int l,int r,int k){
    r++; //转化为左闭右开区间
    while(l<r){
        int j=min_unlocked(__builtin_ctzll(l),__lg(r-l));
        for(int i=l+M>>j;i;i>>=1) v[i]+=k<<j;
        lazy[l+M>>j]+=k; //l+M>>j 即事实上在访问的节点编号
        l+=1<<j;
    }
}

int sum(int l,int r){
    r++;
    int res=0;
    while(l<r){
        int j=min_unlocked(__builtin_ctzll(l),__lg(r-l));
        res+=v[l+M>>j]; 
        for(int i=l+M>>j+1;i;i>>=1) res+=lazy[i]<<j; //把 lazy 扯下来
        l+=1<<j;
    }
    return res;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m;
    for(int i=M+1;i<=M+n;i++) cin>>v[i];
    for(int i=M-1;i;i--) v[i]=v[i<<1]+v[i<<1|1]; //建树
    for(int i=1,opt,l,r,k;i<=m;i++){
        cin>>opt>>l>>r;
        switch(opt){
            case(1):{
                cin>>k;
                add(l,r,k);
                break;
            }
            case(2):{
                cout<<sum(l,r)<<'\n';
                break;
            }
        }
    }
    return 0;
}

复杂度分析

空间复杂度 O(n)，时间复杂度最坏 O(n\log{}^2n)。

但是，由于常数极小，其运行速度甚至接近于一般树状数组。