; 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)))

OyBmZW53aWNrIHRyZWVzCgooZGVmaW5lIHNpemUgMTAwKQoKKGRlZmluZSBmZW4gKG1ha2UtdmVjdG9yICgrIHNpemUgMSkgMCkpCgooZGVmaW5lIChsc2IgaSkgKGxvZ2FuZCBpICgtIGkpKSkKCihkZWZpbmUgKGluY3IgaSBrKSA7IGFkZCBrIHRvIGVsZW1lbnQgYXQgaW5kZXggaQogIChkbyAoKGkgaSAoKyBpIChsc2IgaSkpKSkKICAgICAgKCg8IHNpemUgaSkpCiAgICAodmVjdG9yLXNldCEgZmVuIGkgKCsgKHZlY3Rvci1yZWYgZmVuIGkpIGspKSkpCgooZGVmaW5lIChzdW0gaSkgOyBjdW11bGF0aXZlIHN1bSB0aHJvdWdoIGluZGV4IGkKICAobGV0IGxvb3AgKChpIGkpIChzdW0gMCkpCiAgICAoaWYgKHplcm8/IGkpIHN1bQogICAgICAobG9vcCAoLSBpIChsc2IgaSkpCiAgICAgICAgICAgICgrIHN1bSAodmVjdG9yLXJlZiBmZW4gaSkpKSkpKQoKKGRvICgobiAxICgrIG4gMSkpKSAoKDwgMTAwIG4pKSAoaW5jciBuIG4pKQoKKGRpc3BsYXkgZmVuKSAobmV3bGluZSkKCihkZWZpbmUtc3ludGF4IGFzc2VydAogIChzeW50YXgtcnVsZXMgKCkKICAgICgoYXNzZXJ0IGV4cHIgcmVzdWx0KQogICAgICAoaWYgKG5vdCAoZXF1YWw/IGV4cHIgcmVzdWx0KSkKICAgICAgICAgIChmb3ItZWFjaCBkaXNwbGF5IGAoCiAgICAgICAgICAgICNcbmV3bGluZSAiZmFpbGVkIGFzc2VydGlvbjoiICNcbmV3bGluZQogICAgICAgICAgICBleHByICNcbmV3bGluZSAiZXhwZWN0ZWQ6ICIgLHJlc3VsdAogICAgICAgICAgICAjXG5ld2xpbmUgInJldHVybmVkOiAiICxleHByICNcbmV3bGluZSkpKSkpKQoKKGRlZmluZSAoZ2F1c3MgbikgKCogbiAoKyBuIDEpIDEvMikpCgooZG8gKChuIDEgKCsgbiAxKSkpICgoPCAxMDAgbikpCiAgKGFzc2VydCAoc3VtIG4pIChnYXVzcyBuKSkp