import random
from fenwick_range import FenwickRange

def test_basic():
    fr = FenwickRange(5)
    fr.range_add(2, 4, 3)
    assert fr.range_sum(1, 5) == 9
    assert fr.range_sum(2, 4) == 9
    assert fr.range_sum(1, 1) == 0
    assert fr.range_sum(5, 5) == 0

def test_multiple():
    fr = FenwickRange(6)
    fr.range_add(1, 6, 1)
    fr.range_add(3, 5, 2)
    arr = [1,1,3,3,3,1]
    for i in range(1,7):
        assert fr.prefix_sum(i) == sum(arr[:i])
    assert fr.range_sum(2,4) == 1+3+3

def test_random_vs_naive():
    n=20
    fr=FenwickRange(n)
    arr=[0]*n
    rng=random.Random(42)
    for _ in range(200):
        if rng.random()<0.5:
            l=rng.randint(1,n); r=rng.randint(l,n); v=rng.randint(-5,5)
            fr.range_add(l,r,v)
            for i in range(l-1,r): arr[i]+=v
        else:
            l=rng.randint(1,n); r=rng.randint(l,n)
            assert fr.range_sum(l,r)==sum(arr[l-1:r]), (l,r)
    # prefix
    for i in range(1,n+1):
        assert fr.prefix_sum(i)==sum(arr[:i])

def test_bounds():
    fr=FenwickRange(3)
    try:
        fr.range_add(0,2,1); raise SystemExit("no raise")
    except IndexError: pass
    try:
        fr.range_add(1,4,1); raise SystemExit("no raise")
    except IndexError: pass
    try:
        fr.range_add(2,1,1); raise SystemExit("no raise")
    except IndexError: pass
    try:
        fr.range_sum(1,4); raise SystemExit("no raise")
    except IndexError: pass
    try:
        fr.prefix_sum(4); raise SystemExit("no raise")
    except IndexError: pass

def test_empty():
    fr=FenwickRange(0)
    # no operations valid
    pass

if __name__=="__main__":
    for name in [n for n in globals() if n.startswith("test_")]:
        globals()[name]()
    print("ALL PASS")