线段树

#include<cstdio>
#pragma warning (disable:4996)
using namespace std;
int a[10001];

//结构体，存线段树
struct node
{
    int l, r, v;
}tree[40001];

//建树
void make_tree(int p, int x, int y)
{
    tree[p].l = x;
    tree[p].r = y;
    if (x < y)
    {
        int mid = (x + y) / 2;
        make_tree(p * 2, x, mid);
        make_tree(p * 2 + 1, mid, y);
    }
    if (x == y) return;
}

//储值
int input(int p)
{
    if (tree[p].l == tree[p].r)
    {
        tree[p].v = a[tree[p].l];
        return tree[p].v;
    }
    tree[p].v = input(tree[p * 2].v) + input(tree[p * 2 + 1].v);
    return tree[p].v;
}

//单点修改
void change(int p, int x, int V)
{
    tree[p].v += V;
    if (tree[p].l == tree[p].r) return;
    if (x <= tree[p * 2].r)
        change(p * 2, x, V);
    if (x >= tree[p * 2 + 1].r)
        change(p * 2 + 1, x, V);
}

//查询*(计算xy区间内数的和)
int total = 0;
int find(int x, int y, int p)
{
    if (tree[p].l >= x && tree[p].r <= y)
    {
        total += tree[p].v;
        return total;
    }
    if (x <= tree[p * 2].r)
        find(x, y, p * 2);
    if (x >= tree[p * 2 + 1].l)
        find(x, y, p * 2 + 1);
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    make_tree(1, 1, n);//建立线段树
    for (int i = 1; i <= m; i++)
    {
        int A, x, y, k;
        scanf("%d", &A);
        if (A == 1)
        {
            scanf("%d %d %d", &x, &y, &k);
            for (int j = x; j <= y; j++)
                change(1, j, k);
        }
        else if (A == 2)
        {
            scanf("%d %d", &x, &y);
            printf("%d", find(x, y, 1));
        }
    }
}