Segment Tree

using System;

namespace SegmentTree {
    class SegmentTree {
        int l;
        int r;
        long add;
        long sum;
        SegmentTree lson, rson;

        public SegmentTree(int l, int r, int[] vals) {
            this.l = l;
            this.r = r;
            this.add = 0;
            this.sum = 0;
            if (l != r) {
                this.lson = new SegmentTree(l, (l + r) / 2, vals);
                this.rson = new SegmentTree((l + r) / 2 + 1, r, vals);
                this.sum = this.lson.add + this.lson.sum + this.rson.add + this.rson.sum;
            } else {
                this.lson = null;
                this.rson = null;
                this.add = vals[l];
            }
        }

        public void Add(int l, int r, long val) {
            if (l > this.r || r < this.l) {
                return;
            }
            if (l <= this.l && r >= this.r) {
                this.add += val;
                return;
            }
            this.lson.Add(l, r, val);
            this.rson.Add(l, r, val);
            this.sum = this.lson.add * (this.lson.r - this.lson.l + 1) + this.lson.sum + this.rson.add * (this.rson.r - this.rson.l + 1) + this.rson.sum;
        }

        public long Sum(int l, int r) {
            if (l > this.r || r < this.l) {
                return 0;
            }
            if (l <= this.l && r >= this.r) {
                return this.add * (this.r - this.l + 1) + this.sum;
            }
            return this.add * (Math.Min(r, this.r) - Math.Max(l, this.l) + 1) + this.lson.Sum(l, r) + this.rson.Sum(l, r);
        }
    }
}