1

我目前正在解决段树上的问题。我认为这个问题需要惰性传播概念来解决。由于我对这个概念很陌生，所以我的代码有问题。

简而言之，问题如下：

最初，所有数组元素都是 0，它们的索引为 0 到 N-1

命令 1. 0 xyv - 将 x 和 y 之间的每个数组索引的值更新为 v

命令 2. 1 xy - 输出数组索引 x 和 y 之间所有数字的总和。

输入以整数 T (≤ 5) 开头，表示测试用例的数量。

每个案例包含两个整数 n (1 ≤ n ≤ 105) 和 q (1 ≤ q ≤ 50000)。接下来 q 行中的每一行都包含以下形式之一的任务：

0 xyv (0 ≤ x ≤ y < n, 1 ≤ v ≤ 1000)

1 xy (0 ≤ x ≤ y < n) 对于每个案例，首先打印案例编号。然后对于每个查询“1 x y”，打印 x 和 y 之间所有数组元素的总和。这是我的尝试：

template<class T>
class SegmentTree
{
        T *tree,*update_tree;
        long size;

        public:
            SegmentTree(long N)
            {
                long x= (long)ceil(log2(N))+1;
                long size = 2*(long)pow(2,x);

                tree = new T[size];
                update_tree = new T[size];

                memset(tree,0,sizeof(tree));
                memset(update_tree,0,sizeof(update_tree));
            }

            void update(long node, long start, long end, long i, long j, long val)
            {
                if(start>j || end<i) return;
                if(start>=i && end<=j){
                    if(start==end){
                        tree[node]+=val;
                        return;
                    }
                    tree[node]+=val;
                    update_tree[2*node] += val;
                    update_tree[2*node+1]+=val;
                    return;
                }

                    long mid = (start+end)/2;
                update(2*node,start,mid,i,j,val);
                update(2*node+1,mid+1,end,i,j,val);
            }

            T query(long node, long start, long end, long i, long j, long val)
            {
                if(start>j || end<i) return -1;

                if(start>=i && end<=j)
                    return ((tree[node]+val)*(end-start+1));



                long a,b;
                a = update_tree[2*node];
                b = update_tree[2*node+1];

                 long mid = (start+end)/2;
                long val1 = query(2*node,start,mid,i,j,val+a);
                long val2 = query(2*node+1,mid+1,end,i,j,val+b);

                if(val1==-1)
                    return val2;
                if(val2==-1)
                    return val1;

                return val1+val2;

            }

};

int main()
{   
    long N,q,x,y,res;
    int tc=1, T,v,d;

    scanf("%d",&T);

    while(tc<=T)
    {
        scanf("%ld %ld",&N,&q);
        SegmentTree<long>s(N);

        printf("Case %d:\n",tc++);
        while(q--){
            scanf("%d",&d);
            if(!d){
                scanf("%ld %ld %d",&x,&y,&v);
                s.update(1,0,N-1,x,y,v);
            }
            else{
                scanf("%ld %ld",&x,&y);
                res = s.query(1,0,N-1,x,y,0);
                printf("%ld\n",res);
            }
        }
    }
    return 0;
}
4

0 回答 0