这个板子有什么问题??求教

P3372 【模板】线段树 1

SuAnRan @ 2023-05-14 16:54:29

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long LL;

const int N = 1e5 + 7;

LL sum[500000], easy[500000]; // Sum求和数组, 懒惰数组
LL A[500000], n, m;

void pushUP(int x)
{
    sum[x] = sum[x * 2] + sum[x * 2 + 1];
}

void Build(int l, int r, int x) // 建立线段树
{
    if(l == r) 
    {
        sum[x] = A[l];
        return;
    }

    int m = l + r >> 1;
    Build(l, m, x * 2);
    Build(m + 1, r, x * 2 + 1);

    pushUP(x);
}

void point_Update(int L, int C, int l, int r, int x) // 单点修改
{
    if(l == r) 
    {
        sum[x] += C;
    }

    int m = l + r >> 1;
    if(L <= m) point_Update(L, C, l, m, x * 2);
    else point_Update(L, C, m + 1, r, x * 2 + 1);

    pushUP(x);
}

void PushDown(int l, int r, int x) //懒标记下推
{
    if(easy[x])
    {
        easy[x * 2] += easy[x];
        easy[x * 2 + 1] += easy[x];
        //修改sum值

        int mid = l + r >> 1;

        sum[x * 2] += easy[x] * (mid - l + 1);
        sum[x * 2 + 1] += easy[x] * (r - mid);

        easy[x] = 0;

    }
}

void range_Update(int L, int R, int C, int l, int r, int x)  //区间修改
{
    if(l == L && r == R)
    {
        sum[x] += C * (r - l + 1);
        easy[x] += C;
        return ;
    }

    int m = l + r >> 1;

    PushDown(l, r, x);

    if(L <= m) range_Update(L, R, C, l, m, x * 2);
    if(R > m) range_Update(L, R, C, m + 1, r, x * 2 + 1);

    pushUP(x);
}

LL Query(int L, int R, int l, int r, int x) // 查询【L~R】的和
{
    if(L == l && r == R) //如果在
    {
        return sum[x];
    }

    // 否则, 推下标
    PushDown(l, r, x);

    int m = l + r >> 1;

    LL ans = 0;

    if(L <= m) ans += Query(L, R, l, m, x * 2);
    if(R > m) ans += Query(L, R, m + 1, r, x * 2 + 1);

    return ans;
}

int main()
{
    cin >> n >> m;

    for(int i = 1; i <= n; i ++) cin >> A[i];

    Build(1, n, 1);

   while(m --)
   {
       int op;
       cin >> op;
       if(op == 1)
       {
           int l, r, x;
           cin >> l >> r >> x;
           range_Update(l, r, x, 1, n, 1);
       }
       else
       {
          int l, r;
          cin >> l >> r;
          cout << Query(l, r, 1, n, 1) << endl;
       }
   }

}

by hjqhs @ 2023-05-14 17:00:25

你main函数外定义了m 但在部分线段树操作函数中写的是m=(l+r)>>1


by hjqhs @ 2023-05-14 17:00:50

然后不需要point update


|