(* Basic Fenwick implementation *)
(* Also sometimes called a Range Rree *)
(*
Here's how this works. Consider the binary represented integers
1, 2, .... n. Let's define two functions on these: UP and DN.
UP(i) = i + (i land (-i))
DN(i) = i - (i land (-i))
(Here "land" is the bitwise and operation.) It's easy to see what
these functions do when we look at the binary representation of i.
i land (-i) simply extracts the rightmost 1 bit of i. So DN(i) just
takes the rigthmost 1 bit of i and zeros it. UP(i) takes the
rightmost 1 bit of i, zeros it, and carries a 1 to the left.
UP() is a strictly increasing function and DN() is strictly
decreasing.
let UP-PATH(a) be the sequence [a, UP(a), UP(UP(A))...] terminating
right before it exceeds n. Similarly let DN-PATH(b) be [b, DN(b), ...]
terminating right before it reaches 0.
Theorem: if a <= b then UP-PATH(a) and DN-PATH(b) intersect at
precisely one point. furthermore if a>b then these sets have no
intersection.
Proof: The 2nd part is clear because all elements of UP-PATH(a) are
>=a and all elements of DN-PATH(b) are <= b. The result follows.
Similarly if a=b then the two paths clearly intersect only at a.
If a**j.
Here are a couple of additional observations. First of all it's
possible to generalize this scheme to make shorter UP-PATHS and
longer DN-PATHS.
For example by using base 4, we can make the UP-PATHS log_4(n) and
the DN-PATHS 3*log_4(n). If we use base b, then the two bounds are
log_b(n) and (b-1)*log_b(n). An interesting extreme case is b = sqrt(n).
In this case the UP-PATHS are length 2, and the down paths are
length 2*sqrt(n). This kind of approach is useful if there are a
lot more Increments than SumToLeft operations. (Or vice versa,
see below.)
Another observation is that the theorem about these paths having a
unique intersection when a****=m then (m,bit) else (
bit.(i) <- bit.(i) + v;
loop (i + (i land (-i)))
) in
loop i
let lookup (m,bit) i =
let rec loop i ac = if i=0 then ac else
loop (i - (i land (-i))) (ac + bit.(i))
in
loop i 0
(*************************************************************)
open Printf
open Scanf
let ( ++ ) a b = Int64.add a b
let long x = Int64.of_int x
let read_int () = bscanf Scanning.stdib " %d " (fun x -> x)
let read_string () = bscanf Scanning.stdib " %s " (fun x -> x)
let () =
let n = read_int() in
let a = read_string() in
let b = read_string() in
let toind a i = (int_of_char a.[i-1]) - (int_of_char 'A') in
let q = Array.make 26 [] in
let perm = Array.make (n+1) 0 in
for i=1 to n do
q.(toind a i) <- i::q.(toind a i)
done;
for i=n downto 1 do
perm.(i) <- List.hd q.(toind b i);
q.(toind b i) <- List.tl q.(toind b i)
done;
let rec loop f i ac = if i = 0 then ac else
let ac = ac ++ (long (lookup f perm.(i))) in
loop (insert f 1 perm.(i)) (i-1) ac
in
printf "%Ld\n" (loop (init n) n 0L)
**