萌新刚学线段树,线段树样例不过求调
查看原帖
萌新刚学线段树,线段树样例不过求调
492773
_cpp楼主2023/8/2 21:35

rt

#include<bits/stdc++.h>
using namespace std;
long long n,m,tree[2000010],a[500010],as[2000010];
void bulidtree(long long k,long long l,long long r) //建立线段树
{
    if(l == r){
        tree[k] = a[l];
        return;
    }
    long long mid = (l + r) / 2;
    bulidtree(k * 2,l,mid);
    bulidtree(k * 2 + 1,mid + 1,r);
    tree[k] = tree[k * 2] + tree[k * 2 + 1]; 
}
long long find(long long k,long long x,long long l,long long r) //查找点
{
    if(l == r && l == x) return as[k];
    long long mid = (l + r) / 2;
    if(x <= mid) return find(k * 2,x,l,mid) + as[k];
    else return find(k * 2 + 1,x,mid + 1,r) + as[k];
}
void change(long long k,long long l,long long r,long long x,long long y,long long v)//区间累加,这里没用懒标记,用了延迟标记
{ 
    if(l > y || r < x) return ;
    if(l >= x && r <= y){
        as[k] += v;
        return;
    }
    long long mid = (l + r) / 2;
    change(k * 2,l,mid,x,y,v);
    change(k * 2 + 1,mid + 1,r,x,y,v);
}
int main()
{
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> a[i];
    bulidtree(1,1,n);
    long long x,y,f,k;
    for(int i = 1;i <= m;i++){
        cin >> f;
        if(f == 1) cin >> x >> y >> k,change(1,1,n,x,y,k);
        if(f == 2) cin >> x,cout << find(1,x,1,n) << "\n";
    }
    return 0;
}
2023/8/2 21:35
加载中...