JAVA+线段树, #8#9#10三测试点RE

import java.util.*;
public class Main {
    public static class Node {
        int l,r;
        long value;
        long lazy;
    }

    Node[] tree = new Node[100010*4];;// 存4*N长度的线段树
    public int[] arr = new int[100010]; // 存区间数据

    // 建树, 从index为1开始递归向下建树 (中序遍历)
    void build(int index, int l, int r) {
        tree[index].l = l;
        tree[index].r = r;
        if(l == r)  {
            tree[index].value = arr[l];
            return;
        }
        int mid = (l+r)/2;
        build(index*2, l, mid);
        build(index*2+1, mid+1, r);
        tree[index].value = tree[2*index].value + tree[2*index+1].value;
    }

    // 向下传递lazy标记
    void lazy_down(int index) {
        if(tree[index].l == tree[index].r) {
            tree[index].lazy = 0;
            return;
        }

        if(tree[index].lazy == 0)   return;

        tree[2*index].value += tree[index].lazy*(tree[2*index].r - tree[2*index].l + 1);
        tree[2*index+1].value += tree[index].lazy*(tree[2*index+1].r - tree[2*index+1].l + 1);

        tree[2*index].lazy += tree[index].lazy;
        tree[2*index+1].lazy += tree[index].lazy;

        tree[index].lazy = 0;

        lazy_down(2*index);
        lazy_down(2*index+1);
    }

    // 区间修改, 覆盖区间则lazy标记
    void change(int index, int l, int r, int x) {
        if(tree[index].l > r || tree[index].r < l)  return;

        if(tree[index].l >= l && tree[index].r <= r) {
            tree[index].lazy += x;
            tree[index].value += (long) x * (tree[index].r - tree[index].l + 1);
            return ;
        }

        lazy_down(index);
        int mid = (tree[index].l + tree[index].r) / 2;
        if(mid < r) change(2 * index + 1, l, r, x);
        if(mid >= l ) change(2 * index, l, r, x);

        tree[index].value = tree[2 * index].value + tree[2 * index + 1].value;

    }

    long ask_sum(int index, int l, int r) {
        if(tree[index].l > r || tree[index].r < l)  return 0;

        if(tree[index].l >= l && tree[index].r <= r)
            return tree[index].value;

        lazy_down(index);
        long ans = 0;
        int mid = (tree[index].l + tree[index].r) / 2;
        if(mid < r) ans += ask_sum(2 * index + 1, l, r);
        if(mid >= l ) ans += ask_sum(2 * index, l, r);

        return ans;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        int n = s.nextInt();
        int m = s.nextInt();

        Main main = new Main();
        for (int i = 0; i < main.arr.length; i++) {
            main.tree[i] = new Main.Node();
        }

        for (int i = 1; i <= n; i++) {
            main.arr[i] = s.nextInt();  
        }

        main.build(1, 1, n);
        for (int i = 0; i < m; i++) {
            int model = s.nextInt();
            if(model == 1) {
                int l = s.nextInt();
                int r = s.nextInt();
                int x = s.nextInt();
                main.change(1, l, r, x);
            }
            else {
                int l = s.nextInt();
                int r = s.nextInt();
                System.out.println(main.ask_sum(1, l, r));
            }
        }
    }
}