' Prefix Sum — computes running sum and range sum queries
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL arr(1000) AS LONG
    LOCAL prefix(1000) AS LONG
    LOCAL n AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL total AS LONG
    LOCAL rangeSum AS LONG
    LOCAL leftIdx AS LONG
    LOCAL rightIdx AS LONG
    LOCAL lineStr AS STRING
    LOCAL elemStr AS STRING
    n = 40
    PRINT "============================================"
    PRINT "          PREFIX SUM (Cumulative Sum)"
    PRINT "============================================"
    PRINT ""
    PRINT "Original array:"
    PRINT ""
    FOR i = 0 TO n - 1
        arr(i) = (i * 7 + 13) MOD 20
    NEXT i
    lineStr = ""
    FOR i = 0 TO n - 1
        elemStr = STR$(arr(i))
        DO WHILE LEN(elemStr) < 3
            elemStr = " " + elemStr
        LOOP
        lineStr = lineStr + elemStr + " "
        IF (i + 1) MOD 10 = 0 THEN
            PRINT lineStr
            lineStr = ""
        END IF
    NEXT i
    IF lineStr <> "" THEN
        PRINT lineStr
    END IF
    PRINT ""
    total = 0
    FOR i = 0 TO n - 1
        total = total + arr(i)
        prefix(i) = total
    NEXT i
    PRINT "Prefix sum:"
    PRINT ""
    lineStr = ""
    FOR i = 0 TO n - 1
        elemStr = STR$(prefix(i))
        DO WHILE LEN(elemStr) < 4
            elemStr = " " + elemStr
        LOOP
        lineStr = lineStr + elemStr + " "
        IF (i + 1) MOD 10 = 0 THEN
            PRINT lineStr
            lineStr = ""
        END IF
    NEXT i
    IF lineStr <> "" THEN
        PRINT lineStr
    END IF
    PRINT ""
    PRINT "Range sums (using prefix array):"
    PRINT ""
    FOR i = 0 TO 9
        leftIdx = i * 2
        rightIdx = i * 2 + 4
        IF rightIdx >= n THEN
            rightIdx = n - 1
        END IF
        IF leftIdx <= rightIdx THEN
            rangeSum = 0
            FOR j = leftIdx TO rightIdx
                rangeSum = rangeSum + arr(j)
            NEXT j
            PRINT "Range(" + STR$(leftIdx) + "," + STR$(rightIdx) + ") = " + STR$(rangeSum)
        END IF
    NEXT i
    PRINT ""
    PRINT "Verification using prefix array:"
    PRINT ""
    FOR i = 0 TO 9
        leftIdx = i * 2
        rightIdx = i * 2 + 4
        IF rightIdx >= n THEN
            rightIdx = n - 1
        END IF
        IF leftIdx <= rightIdx THEN
            IF leftIdx = 0 THEN
                rangeSum = prefix(rightIdx)
            ELSE
                rangeSum = prefix(rightIdx) - prefix(leftIdx - 1)
            END IF
            PRINT "Prefix range(" + STR$(leftIdx) + "," + STR$(rightIdx) + ") = " + STR$(rangeSum)
        END IF
    NEXT i
    PRINT ""
    PRINT "============================================"
    PRINT "        2D PREFIX SUM (flattened 1D)"
    PRINT "============================================"
    PRINT ""
    LOCAL rows AS LONG
    LOCAL cols AS LONG
    LOCAL mat(400) AS LONG
    LOCAL pref2d(400) AS LONG
    LOCAL r AS LONG
    LOCAL c AS LONG
    LOCAL r1 AS LONG
    LOCAL c1 AS LONG
    LOCAL r2 AS LONG
    LOCAL c2 AS LONG
    LOCAL sumVal AS LONG
    LOCAL s1 AS LONG
    LOCAL s2 AS LONG
    LOCAL s3 AS LONG
    LOCAL s4 AS LONG
    rows = 6
    cols = 8
    PRINT "2D matrix (" + STR$(rows) + "x" + STR$(cols) + "):"
    PRINT ""
    FOR r = 0 TO rows - 1
        lineStr = ""
        FOR c = 0 TO cols - 1
            mat(r * cols + c) = (r * 3 + c * 5 + 7) MOD 10
            elemStr = STR$(mat(r * cols + c))
            lineStr = lineStr + " " + elemStr + " "
        NEXT c
        PRINT lineStr
    NEXT r
    PRINT ""
    total = 0
    FOR r = 0 TO rows - 1
        FOR c = 0 TO cols - 1
            total = total + mat(r * cols + c)
            s1 = 0
            s2 = 0
            s3 = 0
            IF r > 0 THEN
                s1 = pref2d((r - 1) * cols + c)
            END IF
            IF c > 0 THEN
                s2 = pref2d(r * cols + (c - 1))
            END IF
            IF r > 0 AND c > 0 THEN
                s3 = pref2d((r - 1) * cols + (c - 1))
            END IF
            pref2d(r * cols + c) = total - s1 - s2 + s3
        NEXT c
    NEXT r
    PRINT "Prefix sum matrix:"
    PRINT ""
    FOR r = 0 TO rows - 1
        lineStr = ""
        FOR c = 0 TO cols - 1
            elemStr = STR$(pref2d(r * cols + c))
            DO WHILE LEN(elemStr) < 4
                elemStr = " " + elemStr
            LOOP
            lineStr = lineStr + elemStr + " "
        NEXT c
        PRINT lineStr
    NEXT r
    PRINT ""
    r1 = 1
    c1 = 1
    r2 = 4
    c2 = 6
    sumVal = 0
    FOR r = r1 TO r2
        FOR c = c1 TO c2
            sumVal = sumVal + mat(r * cols + c)
        NEXT c
    NEXT r
    s1 = pref2d(r2 * cols + c2)
    s2 = 0
    s3 = 0
    s4 = 0
    IF r1 > 0 THEN
        s2 = pref2d((r1 - 1) * cols + c2)
    END IF
    IF c1 > 0 THEN
        s3 = pref2d(r2 * cols + (c1 - 1))
    END IF
    IF r1 > 0 AND c1 > 0 THEN
        s4 = pref2d((r1 - 1) * cols + (c1 - 1))
    END IF
    rangeSum = s1 - s2 - s3 + s4
    PRINT "Sum of submatrix (1,1)-(4,6):"
    PRINT "  Direct: " + STR$(sumVal)
    PRINT "  Prefix: " + STR$(rangeSum)
    IF sumVal = rangeSum THEN
        PRINT "  PASS"
    ELSE
        PRINT "  FAIL"
    END IF
    PRINT ""
    PRINT "============================================"
    PRINT "        DIFFERENCE ARRAY (inverse prefix)"
    PRINT "============================================"
    PRINT ""
    LOCAL diff(1000) AS LONG
    LOCAL restored(1000) AS LONG
    FOR i = 0 TO n - 1
        IF i = 0 THEN
            diff(i) = arr(i)
        ELSE
            diff(i) = arr(i) - arr(i - 1)
        END IF
    NEXT i
    PRINT "Difference array:"
    lineStr = ""
    FOR i = 0 TO n - 1
        elemStr = STR$(diff(i))
        DO WHILE LEN(elemStr) < 4
            elemStr = " " + elemStr
        LOOP
        lineStr = lineStr + elemStr + " "
        IF (i + 1) MOD 10 = 0 THEN
            PRINT lineStr
            lineStr = ""
        END IF
    NEXT i
    IF lineStr <> "" THEN
        PRINT lineStr
    END IF
    PRINT ""
    total = 0
    FOR i = 0 TO n - 1
        total = total + diff(i)
        restored(i) = total
    NEXT i
    PRINT "Restored from differences:"
    lineStr = ""
    FOR i = 0 TO n - 1
        elemStr = STR$(restored(i))
        DO WHILE LEN(elemStr) < 4
            elemStr = " " + elemStr
        LOOP
        lineStr = lineStr + elemStr + " "
        IF (i + 1) MOD 10 = 0 THEN
            PRINT lineStr
            lineStr = ""
        END IF
    NEXT i
    IF lineStr <> "" THEN
        PRINT lineStr
    END IF
    PRINT ""
    PRINT "Prefix sum operations complete"
    FUNCTION = 0
END FUNCTION
