Count Integers in Intervals solution and explanation

class CountIntervals:

    def __init__(self):
        self.intervals = []

    def add(self, left: int, right: int) -> None:
        new_interval = (left, right)
        self.intervals.append(new_interval)
        self.intervals.sort()
        merged_intervals = []
        for current in self.intervals:
            if not merged_intervals or merged_intervals[-1][1] < current[0]:
                merged_intervals.append(current)
            else:
                last = merged_intervals.pop()
                merged_intervals.append((last[0], max(last[1], current[1])))
        self.intervals = merged_intervals

    def count(self) -> int:
        return sum(end - start + 1 for start, end in self.intervals)

#include <vector>
#include <algorithm>
using namespace std;

class CountIntervals {
    vector<pair<int, int>> intervals;

public:
    void add(int left, int right) {
        intervals.emplace_back(left, right);
        sort(intervals.begin(), intervals.end());
        vector<pair<int, int>> merged;
        for (auto &[start, end] : intervals) {
            if (merged.empty() || merged.back().second < start) {
                merged.emplace_back(start, end);
            } else {
                merged.back().second = max(merged.back().second, end);
            }
        }
        swap(intervals, merged);
    }

    int count() const {
        int total = 0;
        for (const auto &[start, end] : intervals) {
            total += (end - start + 1);
        }
        return total;
    }
};

import java.util.TreeMap;

class CountIntervals {
    private TreeMap<Integer, Integer> intervals;
    private int totalCount;

    public CountIntervals() {
        intervals = new TreeMap<>();
        totalCount = 0;
    }

    public void add(int left, int right) {
        Integer low = intervals.floorKey(left);
        if (low != null && intervals.get(low) >= left - 1) {
            left = low;
            right = Math.max(right, intervals.get(low));
            totalCount -= (intervals.get(low) - low + 1);
            intervals.remove(low);
        }

        Integer high = intervals.floorKey(right);
        while (high != null && intervals.get(high) >= right) {
            right = Math.max(right, intervals.get(high));
            totalCount -= (intervals.get(high) - high + 1);
            intervals.remove(high);
            high = intervals.floorKey(right);
        }

        intervals.put(left, right);
        totalCount += (right - left + 1);
    }

    public int count() {
        return totalCount;
    }
}

class CountIntervals {
    constructor() {
        this.intervals = new Map(); // Start position of interval mapped to end position
        this.totalCount = 0;
    }

    add(left, right) {
        let mergedLeft = left, mergedRight = right;
        for (const [start, end] of this.intervals.entries()) {
            if (end >= mergedLeft - 1) {
                mergedLeft = Math.min(mergedLeft, start);
                mergedRight = Math.max(mergedRight, end);
                this.totalCount -= (end - start + 1);
                this.intervals.delete(start);
            }
        }
        this.intervals.set(mergedLeft, mergedRight);
        this.totalCount += (mergedRight - mergedLeft + 1);
    }

    count() {
        return this.totalCount;
    }
}

class CountIntervals {
    left: null | CountIntervals;
    right: null | CountIntervals;
    start: number;
    end: number;
    sum: number;
    constructor(start: number = 0, end: number = 10 ** 9) {
        this.left = null;
        this.right = null;
        this.start = start;
        this.end = end;
        this.sum = 0;
    }

    add(left: number, right: number): void {
        if (this.sum == this.end - this.start + 1) return;
        if (left <= this.start && right >= this.end) {
            this.sum = this.end - this.start + 1;
            return;
        }
        let mid = (this.start + this.end) >> 1;
        if (!this.left) this.left = new CountIntervals(this.start, mid);
        if (!this.right) this.right = new CountIntervals(mid + 1, this.end);
        if (left <= mid) this.left.add(left, right);
        if (right > mid) this.right.add(left, right);
        this.sum = this.left.sum + this.right.sum;
    }

    count(): number {
        return this.sum;
    }
}

/**
 * Your CountIntervals object will be instantiated and called as such:
 * var obj = new CountIntervals()
 * obj.add(left,right)
 * var param_2 = obj.count()
 */

type Node struct {
	left  *Node
	right *Node
	l     int
	r     int
	mid   int
	v     int
	add   int
}

type SegmentTree struct {
	root *Node
}

func newNode(l, r int) *Node {
	return &Node{
		left:  nil,
		right: nil,
		l:     l,
		r:     r,
		mid:   (l + r) / 2,
		v:     0,
		add:   0,
	}
}

func newSegmentTree() *SegmentTree {
	return &SegmentTree{
		root: newNode(1, 1000000001),
	}
}

func (st *SegmentTree) modify(l, r, v int, node *Node) {
	if node == nil {
		node = st.root
	}
	if l > r {
		return
	}
	if node.l >= l && node.r <= r {
		node.v = node.r - node.l + 1
		node.add = v
		return
	}
	st.pushdown(node)
	if l <= node.mid {
		st.modify(l, r, v, node.left)
	}
	if r > node.mid {
		st.modify(l, r, v, node.right)
	}
	st.pushup(node)
}

func (st *SegmentTree) query(l, r int, node *Node) int {
	if node == nil {
		node = st.root
	}
	if l > r {
		return 0
	}
	if node.l >= l && node.r <= r {
		return node.v
	}
	st.pushdown(node)
	v := 0
	if l <= node.mid {
		v += st.query(l, r, node.left)
	}
	if r > node.mid {
		v += st.query(l, r, node.right)
	}
	return v
}

func (st *SegmentTree) pushup(node *Node) {
	node.v = node.left.v + node.right.v
}

func (st *SegmentTree) pushdown(node *Node) {
	if node.left == nil {
		node.left = newNode(node.l, node.mid)
	}
	if node.right == nil {
		node.right = newNode(node.mid+1, node.r)
	}
	if node.add != 0 {
		left := node.left
		right := node.right
		left.add = node.add
		right.add = node.add
		left.v = left.r - left.l + 1
		right.v = right.r - right.l + 1
		node.add = 0
	}
}

type CountIntervals struct {
	tree *SegmentTree
}

func Constructor() CountIntervals {
	return CountIntervals{
		tree: newSegmentTree(),
	}
}

func (ci *CountIntervals) Add(left, right int) {
	ci.tree.modify(left, right, 1, nil)
}

func (ci *CountIntervals) Count() int {
	return ci.tree.query(1, 1000000000, nil)
}

/**
 * Your CountIntervals object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(left,right);
 * param_2 := obj.Count();
 */