Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement