Count Subarrays With Even Odd Ratio II solution and explanation

class BinaryIndexedTree:
    __slots__ = "n", "c"

    def __init__(self, n: int):
        self.n = n
        self.c = [0] * (n + 1)

    def update(self, x: int, delta: int) -> None:
        while x <= self.n:
            self.c[x] += delta
            x += x & -x

    def query(self, x: int) -> int:
        s = 0
        while x:
            s += self.c[x]
            x -= x & -x
        return s


class Solution:
    def countRatioSubarrays(self, nums: list[int], a: int, b: int) -> int:
        n = len(nums)
        s = [0] * (n + 1)
        for i, x in enumerate(nums):
            s[i + 1] = s[i] + (a if x % 2 else -b)

        st = sorted(set(s))
        bit = BinaryIndexedTree(len(st) + 1)
        ans = 0
        for v in s:
            x = bisect_left(st, v) + 1
            ans += bit.query(x)
            bit.update(x, 1)
        return ans

class BinaryIndexedTree {
    private final int n;
    private final int[] c;

    public BinaryIndexedTree(int n) {
        this.n = n;
        this.c = new int[n + 1];
    }

    public void update(int x, int delta) {
        while (x <= n) {
            c[x] += delta;
            x += x & -x;
        }
    }

    public int query(int x) {
        int s = 0;
        while (x > 0) {
            s += c[x];
            x -= x & -x;
        }
        return s;
    }
}

class Solution {
    public long countRatioSubarrays(int[] nums, int a, int b) {
        int n = nums.length;

        long[] s = new long[n + 1];
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + (nums[i] % 2 == 1 ? a : -b);
        }

        long[] st = s.clone();
        Arrays.sort(st);

        int m = 0;
        for (long x : st) {
            if (m == 0 || st[m - 1] != x) {
                st[m++] = x;
            }
        }

        BinaryIndexedTree bit = new BinaryIndexedTree(m + 1);

        long ans = 0;

        for (long v : s) {
            int x = Arrays.binarySearch(st, 0, m, v) + 1;
            ans += bit.query(x);
            bit.update(x, 1);
        }

        return ans;
    }
}

class BinaryIndexedTree {
    int n;
    vector<int> c;

public:
    BinaryIndexedTree(int n)
        : n(n)
        , c(n + 1) {}

    void update(int x, int delta) {
        while (x <= n) {
            c[x] += delta;
            x += x & -x;
        }
    }

    int query(int x) {
        int s = 0;
        while (x > 0) {
            s += c[x];
            x -= x & -x;
        }
        return s;
    }
};

class Solution {
public:
    long long countRatioSubarrays(vector<int>& nums, int a, int b) {
        int n = nums.size();

        vector<long long> s(n + 1);
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + (nums[i] % 2 ? a : -b);
        }

        vector<long long> st = s;
        sort(st.begin(), st.end());
        st.erase(unique(st.begin(), st.end()), st.end());

        BinaryIndexedTree bit(st.size() + 1);

        long long ans = 0;

        for (long long v : s) {
            int x = lower_bound(st.begin(), st.end(), v) - st.begin() + 1;
            ans += bit.query(x);
            bit.update(x, 1);
        }

        return ans;
    }
};

class BinaryIndexedTree {
    private n: number;
    private c: number[];

    constructor(n: number) {
        this.n = n;
        this.c = new Array(n + 1).fill(0);
    }

    update(x: number, delta: number): void {
        while (x <= this.n) {
            this.c[x] += delta;
            x += x & -x;
        }
    }

    query(x: number): number {
        let sum = 0;
        while (x > 0) {
            sum += this.c[x];
            x -= x & -x;
        }
        return sum;
    }
}

function countRatioSubarrays(nums: number[], a: number, b: number): number {
    const n = nums.length;

    const s = new Array<number>(n + 1).fill(0);

    for (let i = 0; i < n; i++) {
        s[i + 1] = s[i] + (nums[i] % 2 === 1 ? a : -b);
    }

    const st = [...s].sort((x, y) => x - y);

    const uniq: number[] = [];
    for (const x of st) {
        if (uniq.length === 0 || uniq[uniq.length - 1] !== x) {
            uniq.push(x);
        }
    }

    const bit = new BinaryIndexedTree(uniq.length + 1);

    let ans = 0;

    for (const v of s) {
        const x = _.sortedIndex(uniq, v) + 1;

        ans += bit.query(x);
        bit.update(x, 1);
    }

    return ans;
}

type BinaryIndexedTree struct {
	n int
	c []int
}

func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
	return &BinaryIndexedTree{
		n: n,
		c: make([]int, n+1),
	}
}

func (bit *BinaryIndexedTree) update(x int, delta int) {
	for x <= bit.n {
		bit.c[x] += delta
		x += x & -x
	}
}

func (bit *BinaryIndexedTree) query(x int) int {
	sum := 0
	for x > 0 {
		sum += bit.c[x]
		x -= x & -x
	}
	return sum
}

func countRatioSubarrays(nums []int, a int, b int) int64 {
	n := len(nums)

	s := make([]int64, n+1)

	for i, x := range nums {
		if x%2 == 1 {
			s[i+1] = s[i] + int64(a)
		} else {
			s[i+1] = s[i] - int64(b)
		}
	}

	st := append([]int64{}, s...)
	sort.Slice(st, func(i, j int) bool {
		return st[i] < st[j]
	})

	uniq := make([]int64, 0, len(st))
	for _, x := range st {
		if len(uniq) == 0 || uniq[len(uniq)-1] != x {
			uniq = append(uniq, x)
		}
	}

	bit := NewBinaryIndexedTree(len(uniq) + 1)

	var ans int64

	for _, v := range s {
		x := sort.Search(len(uniq), func(i int) bool {
			return uniq[i] >= v
		}) + 1

		ans += int64(bit.query(x))
		bit.update(x, 1)
	}

	return ans
}