二维离散化

代码：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e4+10;
struct no
{
    int x1,x2,y1,y2;
}q[N];
bool c[N][N];
ll ans;
int n;
vector<int>a,b;
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>q[i].x1>>q[i].y1>>q[i].x2>>q[i].y2;
        a.push_back(q[i].x1);
        a.push_back(q[i].x2);
        b.push_back(q[i].y1);
        b.push_back(q[i].y2);
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    a.erase(unique(a.begin(),a.end()),a.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    for(int i=0;i<n;i++)
    {
        int x1,y1,x2,y2;
        x1=lower_bound(a.begin(),a.end(),q[i].x1)-a.begin();
        x2=lower_bound(a.begin(),a.end(),q[i].x2)-a.begin();
        y1=lower_bound(b.begin(),b.end(),q[i].y1)-b.begin();
        y2=lower_bound(b.begin(),b.end(),q[i].y2)-b.begin();

        for(int j=x1;j<x2;j++)
        for(int k=y1;k<y2;k++)
        c[j][k]=true;


    }
    for(int i=0;i<a.size()-1;i++)
    for(int j=0;j<b.size()-1;j++)
    if(c[i][j])ans+=(ll)(a[i+1]-a[i])*(b[j+1]-b[j]);
    cout<<ans;

    return 0;
}

线段树

代码：

//建树
#include<bits/stdc++.h>
#define int long long  
using namespace std;
typedef long long ll;
const int N=1e5+10,M=4*N;
int a[N],n,m,t[M],tag[M];
//合并
void push_up(int fa)
{
    t[fa]=t[fa<<1]+t[fa<<1|1];
}
void push_down(int l,int r,int fa)
{
    int mid=l+r>>1;
    //左右子树tree和tag都要更新
    //左子树
    t[fa<<1]+=tag[fa]*(mid-l+1);
    tag[fa<<1]+=tag[fa];
    //右子树
    t[fa<<1|1]+=tag[fa]*(r-mid);
    tag[fa<<1|1]+=tag[fa];
    //该节点懒惰标记还原
    tag[fa]=0;
}
//建树
void build(int fa,int l,int r)//一定注意这里的传参的对应，否则够你调的
{
    //递归出口
    if(l>=r)
    {
        t[fa]=a[l];//树父节点为该节点，此时l=r无所谓
        return;//一定记得终止
    }
    int mid=l+r>>1;//分治
    build(fa<<1,l,mid);//左子树是fa*2
    build(fa<<1|1,mid+1,r);//右子树是fa*2+1
    push_up(fa);//左右子树合并
}
//查询
int query(int ql,int qr,int l,int r,int fa)
{
    int ans=0;//存储结果
    if(ql<=l&&qr>=r)return t[fa];//当查询范围包含了查询区间时就返回
    int mid=l+r>>1;//仍是对区间分治
    //更新懒惰标记
    push_down(l,r,fa);
    if(ql<=mid)ans+=query(ql,qr,l,mid,fa<<1);//左子树
    if(qr>mid)ans+=query(ql,qr,mid+1,r,fa<<1|1);//右子树
    return ans;//结果
}
void update(int ql,int qr,int l,int r,int fa,int k)
{
    if(ql<=l&&qr>=r)
    {
        t[fa]+=k*(r-l+1);
        tag[fa]+=k;//注意这里可能之前就有标记了所以是累加
        return;
    }
    push_down(l,r,fa);//更新懒惰标记
    int mid=l+r>>1;
    if(ql<=mid)update(ql,qr,l,mid,fa<<1,k);
    if(qr>mid)update(ql,qr,mid+1,r,fa<<1|1,k);

    //加完后记得合并
    push_up(fa);
}
void solve()
{
    int op;
    scanf("%lld",&op);
    if(op==2)
    {
        int l,r;
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",query(l,r,1,n,1));
    } 
    else
    {
        int l,r,x;
        scanf("%lld%lld%lld",&l,&r,&x);
        update(l,r,1,n,1,x);
    }
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    build(1,1,n);//father left right
    //for(int i=1;i<=n;i++)printf("%lld ",t[i]);
    while(m--)solve();

    return 0;
}

线段树如何实现单点修改和单点查询？

如果只是询问根节点，那将修改和查询操作的“询问区间”改为【1,1】即可

线段树求区间最值（ST表也可以实现）

这里只需要将建树的函数最后左右子树不合并了，改为求左右子树最大或最小值赋值给根节点。将查询函数改成求最值函数即可

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,M=4*N;
int a[N],t[M];
int n,m;
vector<int>q;
void build(int fa,int l,int r)
{
    if(l==r)
    {
        t[fa]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(fa<<1,l,mid);
    build(fa<<1|1,mid+1,r);
    t[fa]=min(t[fa<<1],t[fa<<1|1]);
}
int minn(int ql,int qr,int l,int r,int fa)
{
    if(ql<=l&&qr>=r)return t[fa];
    int w=1e9;
    int mid=(l+r)>>1;
    if(ql<=mid)w=min(w,minn(ql,qr,l,mid,fa<<1));
    if(qr>mid)w=min(w,minn(ql,qr,mid+1,r,fa<<1|1));
    return w;
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    build(1,1,n);
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        q.push_back(minn(l,r,1,n,1));
    }
    for(auto &p:q)cout<<p<<' ';

    return 0;
}

线段树实现区间赋值（修改）（结合分块思想）

扶苏的问题

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
//data就存最值 set是否重置  add相当于懒惰标记
struct no
{
    int data,add=0;
    bool set=0;
}tr[4*N];
int n,m,num,a[N];
void build(int fa,int l,int r)
{
    if(l==r)
    {
     tr[fa].data=a[l];
     num=max(num,fa);//num存最大节点编号，即节点个数
     return;
    }
    int mid=l+r>>1;
    build(fa<<1,l,mid);
    build(fa<<1|1,mid+1,r);
    //num=max(tr[fa<<1],tr[fa<<1|1]);
    tr[fa].data=max(tr[fa<<1].data,tr[fa<<1|1].data);

}
//惰性标记
void push_down(int fa)
{
    if(tr[fa].set)//被重置过
    {
        tr[fa].set=0;
        tr[fa].add=0;
        tr[fa<<1].add=0;
        tr[fa<<1].set=1;
        tr[fa<<1].data=tr[fa].data;
        tr[fa<<1|1].add=0;
        tr[fa<<1|1].set=1;
        tr[fa<<1|1].data=tr[fa].data;
    }
    else 
    {
        tr[fa<<1].add+=tr[fa].add;
        tr[fa<<1].data+=tr[fa].add;//data时刻表示当前节点的最大值
        tr[fa<<1|1].add+=tr[fa].add;
        tr[fa<<1|1].data+=tr[fa].add;
        tr[fa].add=0;
    }
}
//查询区间最值  ql qr是查询区间 l和r是操作范围
int query(int fa,int ql,int qr,int l,int r)
{
    int ans=-1e18;
    //向下查，当到叶子
    if(ql<=l&&qr>=r)return tr[fa].data;
    //需要push——down更新懒惰标记
    push_down(fa);
    int mid=l+r>>1;
    //右子树是mid+1,所以要大于，左子树大于等于
    if(ql<=mid)ans=max(ans,query(fa<<1,ql,qr,l,mid));
    if(qr>mid)ans=max(ans,query(fa<<1|1,ql,qr,mid+1,r));
    return ans; 
}
void update(int fa,int ql,int qr,int l,int r,int k)
{
    if(ql<=l&&qr>=r)
    {
        tr[fa].data+=k;
        tr[fa].add+=k;//惰性标记
        return;
    }
    push_down(fa);
    int mid=l+r>>1;
    if(ql<=mid)update(fa<<1,ql,qr,l,mid,k);
    if(qr>mid)update(fa<<1|1,ql,qr,mid+1,r,k);
    tr[fa].data=max(tr[fa<<1].data,tr[fa<<1|1].data);
}
//修改
void reset(int fa,int ql,int qr,int l,int r,int k)
{
    if(ql<=l&&qr>=r)
    {
        tr[fa].data=k;
        tr[fa].add=0;
        tr[fa].set=1;//重置了
        return;
    }
    push_down(fa);
    int mid=l+r>>1;
    if(ql<=mid)reset(fa<<1,ql,qr,l,mid,k);
    if(qr>mid)reset(fa<<1|1,ql,qr,mid+1,r,k);
    tr[fa].data=max(tr[fa<<1].data,tr[fa<<1|1].data);

}
signed main()
{
    int l,r,k;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",a+i);
    build(1,1,n);
    while(m--)
    {
        int op;
        scanf("%lld",&op);
        //区间修改
        if(op==1)
        {
            scanf("%lld%lld%lld",&l,&r,&k);
            reset(1,l,r,1,n,k);
        }
        else if(op==2)
        {
            scanf("%lld%lld%lld",&l,&r,&k);
            update(1,l,r,1,n,k);
        }
        else 
        {
            scanf("%lld%lld",&l,&r);
            printf("%lld\n",query(1,l,r,1,n));
        }
    }


    return 0;
}