线段树 (经典题目合集)

1.子段乘积

直接暴力做肯定超时
用线段树O(nlogn)
数组要开2e+10，如果开2e5+10就会wa(段错误)RE

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N = 2e6 + 10;
const ll mod=998244353;
ll n,m,k,arr[N];

struct node
{
    ll l,r,sum;
}tree[N];
inline void push_up(ll i)
{
    tree[i].sum=(tree[i*2].sum)%mod*(tree[i*2+1].sum)%mod;
}
inline void build(ll i,ll l,ll r)
{
    tree[i].l=l,tree[i].r=r;
    if(l==r)
    {
        tree[i].sum=arr[l];
        return ;
    }
    ll mid=(l+r)>>1;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    push_up(i);
}
inline ll query(ll i,ll l,ll r)
{
    if(tree[i].l>=l&&tree[i].r<=r)
        return tree[i].sum;
    ll res=1;
    if(tree[i*2].r>=l)
        res=(res*query(i*2,l,r))%mod;
    if(tree[i*2+1].l<=r)
       res=(res*query(i*2+1,l,r))%mod;
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i)
        cin>>arr[i];
    build(1,1,n);
    ll ans=0;
    for(int i=1;i<=n-k;++i)
    {
        ans=max(ans,query(1,i,i+k-1));
    }
    cout<<ans%mod<<endl;
    return 0;
}

P3372 【模板】线段树 1（加法线段树）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+7;
const ll mod=2147483647;
ll n,m;
struct node
{
    ll l,r,sum,lz;
}tree[N];
ll arr[N];
void build(ll i,ll l,ll r,ll arr[])
{
    tree[i].lz=0;//初始化的时候肯定都是0
    tree[i].l=l;
    tree[i].r=r;
    if(l==r)
    {
        tree[i].sum=arr[l];//到达底部单节点才把输入的值赋给你
        return ;
    }
    ll mid=(l+r)/2;
    build(i*2,l,mid,arr);
    build(i*2+1,mid+1,r,arr);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//树已经全部建完了，再从下往上+++，使得上层的树都有了值
    return ;
}
inline void push_down(ll i)
{
    if(tree[i].lz!=0)
    {
        tree[i*2].lz+=tree[i].lz;
        tree[i*2+1].lz+=tree[i].lz;
        ll mid=(tree[i].l+tree[i].r)/2;
        tree[i*2].sum+=tree[i].lz*(mid-tree[i*2].l+1);
        tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-mid);
        tree[i].lz=0;
    }
    return ;
}
inline void add(ll i,ll l,ll r,ll k)
{
    if(tree[i].l>=l&&tree[i].r<=r)
    {
        tree[i].sum+=k*(tree[i].r-tree[i].l+1);
        tree[i].lz+=k;
        return ;
    }
    push_down(i);
    if(tree[i*2].r>=l)
        add(i*2,l,r,k);
    if(tree[i*2+1].l<=r)
        add(i*2+1,l,r,k);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    return ;
}
inline ll searchs(ll i,ll l, ll r)
{
    if(tree[i].l>=l&&tree[i].r<=r)
        return tree[i].sum;
    push_down(i);
    ll num=0;
    if(tree[i*2].r>=l)
        num+=searchs(i*2,l,r);
    if(tree[i*2+1].l<=r)
        num+=searchs(i*2+1,l,r);
    return num;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>arr[i];
    build(1,1,n,arr);//从根节点开始建树
    for(int i=1;i<=m;++i)
    {
        ll tmp;
        cin>>tmp;
        if(tmp==1)
        {
            ll a,b,c;
            cin>>a>>b>>c;
            add(1,a,b,c);//每次修改都是从编号为1开始的，因为编号1是树的顶端，往下分叉
        }
        if(tmp==2)
        {
            ll a,b;
            cin>>a>>b;
            printf("%lld\n",searchs(1,a,b));//编号i的话，每次都是从1开始
        }
    }
    return 0;
}

P3373 【模板】线段树 2（乘法线段树）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+7;
template<typename T>void read(T &x)
{
    x=0;char ch=getchar();ll f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x*=f;
}
ll n,m,arr[N],mod,flag,cn,cm,cw;
struct node
{
    ll l,r,sum,mul,add;//有乘有加，先乘后加
}tree[N];

inline void build(ll i,ll l,ll r)
{
    tree[i].l=l;
    tree[i].r=r;
    tree[i].mul=1;
    if(l==r)
    {
        tree[i].sum=arr[l]%mod;
        return ;
    }
    ll mid=(l+r)>>1;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
}
inline void push_down(ll i)
{
    tree[i*2].sum=(ll)(tree[i].mul*tree[i*2].sum+((tree[i*2].r-tree[i*2].l+1)*tree[i].add)%mod)%mod;
    tree[i*2+1].sum=(ll)(tree[i].mul*tree[i*2+1].sum+((tree[i*2+1].r-tree[i*2+1].l+1)*tree[i].add)%mod)%mod;
    tree[i*2].mul=(ll)(tree[i*2].mul*tree[i].mul)%mod;
    tree[i*2+1].mul=(ll)(tree[i*2+1].mul*tree[i].mul)%mod;
    tree[i*2].add=(ll)(tree[i*2].add*tree[i].mul+tree[i].add)%mod;
    tree[i*2+1].add=(ll)(tree[i*2+1].add*tree[i].mul+tree[i].add)%mod;
    tree[i].mul=1;tree[i].add=0;
}
inline void add(ll i,ll l,ll r,ll k)
{
    if(tree[i].l>=l&&tree[i].r<=r)
    {
        tree[i].add=(ll)(tree[i].add+k)%mod;
        tree[i].sum=(ll)(tree[i].sum+k*(tree[i].r-tree[i].l+1))%mod;
        return ;
    }
    push_down(i);
    tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
    if(tree[i*2].r>=l)
        add(i*2,l,r,k);
    if(tree[i*2+1].l<=r)
        add(i*2+1,l,r,k);
    //ll mid=(tree[i].l+tree[i].r)>>1;
    //if(l<=mid)add(i*2,l,r,k);
    //if(mid<r)add(i*2+1,l,r,k);
    tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
}
inline void mult(ll i,ll l,ll r,ll k)
{
    if(tree[i].l>=l&&tree[i].r<=r)
    {
        tree[i].mul=(tree[i].mul*k)%mod;
        tree[i].add=(tree[i].add*k)%mod;
        tree[i].sum=(tree[i].sum*k)%mod;
        return ;
    }
    push_down(i);
    tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
    if(tree[i*2].r>=l)
        mult(i*2,l,r,k);
    if(tree[i*2+1].l<=r)
        mult(i*2+1,l,r,k);
    //ll mid=(tree[i].l+tree[i].r)>>1;
    //if(l<=mid)mult(i*2,l,r,k);
    //if(mid<r)mult(i*2+1,l,r,k);
    tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
}
inline ll query(ll i,ll l,ll r)
{
    if(tree[i].l>=l&&tree[i].r<=r)
        return tree[i].sum;
    push_down(i);
    ll num=0;
    if(tree[i*2].r>=l)
        num=(num+query(i*2,l,r))%mod;
    if(tree[i*2+1].l<=r)
        num=(num+query(i*2+1,l,r))%mod;
    return num;
    //ll val=0;
    //ll mid=(tree[i].l+tree[i].r)>>1;
    //if(l<=mid)val=(val+query(i*2,l,r))%mod;
    //if(mid<r)val=(val+query(i*2+1,l,r))%mod;
    //return val;
}
int main()
{
    read(n),read(m),read(mod);
    for(int i=1;i<=n;++i)
        read(arr[i]);
    build(1,1,n);
    for(int i=1;i<=m;++i)
    {
        read(flag);
        if(flag==1)
        {
            read(cn),read(cm),read(cw);
            mult(1,cn,cm,cw);
        }
        else if(flag==2){
            read(cn),read(cm),read(cw);
            add(1,cn,cm,cw);
        }
        else {
            read(cn),read(cm);
            cout<<query(1,cn,cm)<<endl;
        }
    }
}

P4145 上帝造题的七分钟2 / 花神游历各国（根号线段树）

P4145 上帝造题的七分钟2 / 花神游历各国

这道题的关键在于，sqrt(1)==1

也就是说，如果一个区间的最大值为1，我们就可以直接跳过这段区间的修改。只有最大值大于1时才有修改的必要。

而题中的数值大小范围在(0,1e12)之间。

我们可以用计算器得知：

每个数至多六次开平方便可得到1

每次暴力修改复杂度为logn，总复杂度nlogn。数据范围只有1e5，因此不用在意常数的影响。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 4e5 + 10;
const ll mod=1000000010;
ll n,m,k,arr[N];
struct node
{
    ll l,r,sum,maxn;
}tree[N];
inline void push_up(ll i)
{
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    tree[i].maxn=max(tree[i*2].maxn,tree[i*2+1].maxn);
}
inline void build(ll i,ll l,ll r)
{
    tree[i].l=l;
    tree[i].r=r;
    if(l==r)
    {
        tree[i].sum=tree[i].maxn=arr[l];
        return ;
    }
    ll mid=(l+r)>>1;
    build(i*2,l,mid);
    build(i*2+1,mid+1,r);
    push_up(i);
}
inline void change(ll i,ll l,ll r)
{
    if(tree[i].l==tree[i].r)
    {
        tree[i].sum=sqrt(tree[i].sum);
        tree[i].maxn=sqrt(tree[i].maxn);
        return ;
    }
    if(tree[i*2].r>=l&&tree[i*2].maxn>1)
        change(i*2,l,r);
    if(tree[i*2+1].l<=r&&tree[i*2+1].maxn>1)
        change(i*2+1,l,r);
    push_up(i);
}
inline ll query(ll i,ll l,ll r)
{
    if(tree[i].l>=l&&tree[i].r<=r)
        return tree[i].sum;
    ll ans=0;
    if(tree[i*2].r>=l)
        ans+=query(i*2,l,r);
    if(tree[i*2+1].l<=r)
        ans+=query(i*2+1,l,r);
    return ans;
}
int main()
{
    ll a,l,r;
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>arr[i];
    build(1,1,n);
    cin>>m;
    while(m--)
    {
        cin>>a>>l>>r;
        if(l>r)swap(l,r);
        if(a==0)
            change(1,l,r);
        else cout<<query(1,l,r)<<endl;
    }
    return 0;
}

线段树 (经典题目合集)

目录

1.子段乘积

P3372 【模板】线段树 1（加法线段树）

P3373 【模板】线段树 2（乘法线段树）

P4145 上帝造题的七分钟2 / 花神游历各国（根号线段树）