Topic Description

Input format

Output format

sample input

3 2
1 2 3
1 2 0
2 1 3

sample output

6

Topic analysis: This should be the most basic segment tree, that is, the revision and summation of the intervals. The code I write is also a template for searching from the Internet. When building a tree, it is recursive to the bottom, that is, leaf nodes, and then back up. Each node records the sum of the intervals and the intervals. Interval modification is almost the same as tree building. If you want to re-optimize, you can use lazy markers, that is, delayed modification. That's almost what it means. Seeking the interval is similar to the previous one. It's a truth!!!

The code is as follows

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int l,r;
    long long sum,poi;
}tree[4040400];
int n,m;
int c,l,r,x;
long long d;
int i;
long long a[1010100];
void build(int p,int l,int r) // Build up trees
{
    tree[p].l=l;tree[p].r=r;
    if (l==r) {
		tree[p].sum=a[l];
		return;
	}
    int mid=(l+r)/2;
    if (l<=mid) build(p*2,l,mid);
    if (r>mid) build(p*2+1,mid+1,r);
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
void spread(int p)
{
    if (tree[p].poi)
    {
        tree[p*2].sum+=(tree[p*2].r-tree[p*2].l+1)*tree[p].poi;
        tree[p*2+1].sum+=(tree[p*2+1].r-tree[p*2+1].l+1)*tree[p].poi;
        tree[p*2].poi+=tree[p].poi;
        tree[p*2+1].poi+=tree[p].poi;
        tree[p].poi=0;
    }
}
void change(int p,int l,int r,long long d)//  Interval modification
{
    if (l<=tree[p].l&&tree[p].r<=r)
    {
        tree[p].sum+=(tree[p].r-tree[p].l+1)*d;
        tree[p].poi+=d;
        return;
    }
    spread(p);
    int mid=(tree[p].l+tree[p].r)/2;
    if (l<=mid) change(p*2,l,r,d);
    if (r>mid) change(p*2+1,l,r,d);
    tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
long long ask(int p,int l,int r)  //Interval query
{
    if (l>tree[p].r||r<tree[p].l) return 0;
    if (l<=tree[p].l&&tree[p].r<=r)
    return tree[p].sum;
    spread(p);
    int mid=(tree[p].l+tree[p].r)/2;
    long long val=0;
    if (l<=mid) val+=ask(p*2,l,r);
    if (r>mid) val+=ask(p*2+1,l,r);
    return val;
}
int main() 
{
    scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&c,&l,&r);
        if (c==1)
        {
            //scanf("%lld",&d);
            change(1,l,l,r);
        }
        else
        printf("%lld\n",ask(1,l,r));
    }
}