萌新刚学OI,线段树求调

rt

#include <bits/stdc++.h>
using namespace std;

#define lson (id << 1)
#define rson (id << 1 | 1) 
#define IAKIOI puts("QwQ")

struct tree
{
    int l, r;
    long long sum, lazy;
}t[400005];

int a[100005], n, T;

//build segment tree
void push_up(int id)
{
    t[id].sum = t[lson].sum + t[rson].sum;
} 

void build(int id, int l, int r)
{
    t[id].l = l, t[id].r = r;
    if (l == r)
    {
        t[id].sum = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    push_up(id);
}

//add 
void push_down(int id, int l, int r)
{
    if (t[id].lazy)
    {
        int mid = (l + r) >> 1;
        t[lson].lazy += t[id].lazy;
        t[rson].lazy += t[id].lazy;

        t[lson].sum += t[id].lazy * (mid - l + 1);
        t[rson].sum += t[id].lazy * (r - mid);
        t[id].lazy = 0;
    }
}

void change(int id, int l, int r, long long x)
{
    int L = t[id].l, R = t[id].r;
    if (l <= L && R <= r)
    {
        t[id].sum += (R - L + 1) * x;
        t[id].lazy += x;
        return;
    }
    int mid = (L + R) >> 1;
    push_down(id, L, R);
    if (l <= mid)     
    {
        change(lson, l, r, x);
    }
    if (r > mid)
    {
        change(rson, l, r, x);
    }
    push_up(id);
}

//query
long long query(int id, int l, int r)
{
    int L = t[id].l, R = t[id].r;
    if (l <= L && R <= r)
    {
        return t[id].sum;
    }
    push_down(id, l, r);
    int mid = (L + R) >> 1;
    long long ans = 0;
    if (l <= mid)     
    {
        ans += query(lson, l, r);
    }
    if (r > mid)
    {
        ans += query(rson, l, r);
    }
    return ans;
}

int main()
{
    scanf("%d%d", &n, &T);
    for (int i = 1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
    }

    build(1, 1, n);

    while (T --)
    {
        int op;
        scanf("%d", &op);
        if (op == 1)
        {
            int x, y, k;
            scanf("%d%d%d", &x, &y, &k);
            change(1, x, y, k);
        }
        else if (op == 2)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%lld\n", query(1, x, y));
        }
    }
    return 0;
} 

线段树自学的

可能出一些很离谱的错误 ( 但是我查不出来 )