| 1 | void fht(vi &arr, bool inv=false, int l=0, int r=-1) { |
| 2 | if (r == -1) { fht(arr,inv,0,size(arr)); return; } |
| 3 | if (l+1 == r) return; |
| 4 | int k = (r-l)/2; |
| 5 | if (!inv) fht(arr, inv, l, l+k), fht(arr, inv, l+k, r); |
| 6 | rep(i,l,l+k) { int x = arr[i], y = arr[i+k]; |
| 7 | if (!inv) arr[i] = x-y, arr[i+k] = x+y; |
| 8 | else arr[i] = (x+y)/2, arr[i+k] = (-x+y)/2; } |
| 9 | if (inv) fht(arr, inv, l, l+k), fht(arr, inv, l+k, r); } |
| 10 | // vim: cc=60 ts=2 sts=2 sw=2: |