; fenwick trees

(define size 100)

(define fen (make-vector (+ size 1) 0))

(define (lsb i) (logand i (- i)))

(define (incr i k) ; add k to element at index i
  (do ((i i (+ i (lsb i))))
      ((< size i))
    (vector-set! fen i (+ (vector-ref fen i) k))))

(define (sum i) ; cumulative sum through index i
  (let loop ((i i) (sum 0))
    (if (zero? i) sum
      (loop (- i (lsb i))
            (+ sum (vector-ref fen i))))))

(do ((n 1 (+ n 1))) ((< 100 n)) (incr n n))

(display fen) (newline)

(define-syntax assert
  (syntax-rules ()
    ((assert expr result)
      (if (not (equal? expr result))
          (for-each display `(
            #\newline "failed assertion:" #\newline
            expr #\newline "expected: " ,result
            #\newline "returned: " ,expr #\newline))))))

(define (gauss n) (* n (+ n 1) 1/2))

(do ((n 1 (+ n 1))) ((< 100 n))
  (assert (sum n) (gauss n)))