线段树

使用线段树进行多点更改和多点查询

建树

#include<iostream>

using namespace std;
typedef long long ll;

const int N=2e5+10;

struct segm
{
    int l,r;
    ll v;
} tr[N*4];
ll a[N];

void push_up(int u)
{
    tr[u].v=tr[u>>1].v+tr[u>>1|1].v;
}

//建树
void build(int u,int l,int r)
{
    //叶子节点
    if(l==r)
    {
        tr[u]={l,r,a[l]};
        return ;
    }
    tr[u]={l,r};
    int mid=l+r>>1;
    build(u>>1,l,mid),build(u>>1|1,mid+1,r);
    push_up(u);
}

//单点修改
void modify(int u,int x,ll d)
{
    if(tr[u].l==tr[u].r)
    {
        tr[u].v=d;
        return ;
    }

    int mid=tr[u].l+tr[u].r>>1;
    if(mid>=x) modify(u>>1,x,d);
    else modify(u>>1|1,x,d);
    push_up(u);
}

//多点修改
void multi_modify(int u,int l,int r,ll d)
{
    if(tr[u].l==tr[u].r)
    {
        tr[u].v=d;
        return;
    }

    int mid=tr[u].l+tr[u].r>1;
    if(mid>=l) multi_modify(u>>1,l,r,d);
    if(mid<r) multi_modify(u>>1|1,l,r,d);
    push_up(u);
}

//区域查询
ll query(int u,int l,int r)
{
    if(tr[u].l>=l&&tr[u].r<=r)
    {
        return tr[u].v;
    }
    ll sum=0;
    int mid=tr[u].l+tr[u].r>>1;
    if(mid>=l) sum=query(u>>1,l,r);
    if(mid>r) sum+=query(u>>1|1,l,r);
    return sum;
}

int main()
{
    build(1,1,n);
}