You are an expert in writing code in many different languages. Your goal is to perform code completion for the following code, keeping in mind the rest of the code and the file meta data.
    Metadata details:
    filename: fenwick_tree.go
    path of file: ./repos/codeforces-go/copypasta
    
    the code of the file until where you have to start completion: package copypasta

import (
	"math"
	"sort"
)

/* 树状数组（Fenwick Tree），二叉索引树（Binary Index Tree, BIT）
https://en.wikipedia.org/wiki/Fenwick_tree
【推荐阅读】带你发明树状数组！https://leetcode.cn/problems/range-sum-query-mutable/solution/dai-ni-fa-ming-shu-zhuang-shu-zu-fu-shu-lyfll/

可视化 https://visualgo.net/zh/fenwicktree

todo 树状数组延申应用 https://www.luogu.com.cn/blog/kingxbz/shu-zhuang-shuo-zu-zong-ru-men-dao-ru-fen
 浅谈树状数组的优化及扩展 https://www.luogu.com.cn/blog/countercurrent-time/qian-tan-shu-zhuang-shuo-zu-you-hua
 浅谈树状数组套权值树 https://www.luogu.com.cn/blog/bfqaq/qian-tan-shu-zhuang-shuo-zu-quan-zhi-shu
https://oi-wiki.org/ds/bit/
https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/FenwickTree.java.html

- [307. 区域和检索 - 数组可修改](https://leetcode.cn/problems/range-sum-query-mutable/) *模板题
   - https://www.luogu.com.cn/problem/P3374
- [315. 计算右侧小于当前元素的个数](https://leetcode.cn/problems/count-of-smaller-numbers-after-self/) *逆序对
- [2426. 满足不等式的数对数目](https://leetcode.cn/problems/number-of-pairs-satisfying-inequality/) 2030
- [493. 翻转对](https://leetcode.cn/problems/reverse-pairs/)
- [327. 区间和的个数](https://leetcode.cn/problems/count-of-range-sum/)

关于逆序对，见下面的 cntInversions

https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
https://atcoder.jp/contests/arc075/tasks/arc075_c
静态区间种类 - 离线做法
    https://www.luogu.com.cn/problem/P1972
    https://atcoder.jp/contests/abc174/tasks/abc174_f
    https://codeforces.com/problemset/problem/246/E 2400
置换 LC2179 https://leetcode.cn/problems/count-good-triplets-in-an-array/
- 同样的置换思想 LC1713 https://leetcode.cn/problems/minimum-operations-to-make-a-subsequence/
题目推荐 https://cp-algorithms.com/data_structures/fenwick.html#toc-tgt-12
树状数组的性质能使其支持动态 [1,x] 或 [x,n] 范围上的最值更新查询等操作
    https://codeforces.com/problemset/problem/629/D 2000
    https://codeforces.com/problemset/problem/1635/F 2800
好题 https://www.luogu.com.cn/problem/P2345 https://www.luogu.com.cn/problem/P5094
多变量统计 https://codeforces.com/problemset/problem/1194/E
         T4 https://www.nowcoder.com/discuss/1022136
最多交换 k 次相邻字母后，得到的最小字典序
- LC1505 https://leetcode.cn/problems/minimum-possible-integer-after-at-most-k-adjacent-swaps-on-digits/
LC2921 https://leetcode.cn/problems/maximum-profitable-triplets-with-increasing-prices-ii/
https://codeforces.com/contest/1915/problem/F 1500
区间包含计数 https://codeforces.com/problemset/problem/652/D 1800
长为 k 的上升子序列个数 https://codeforces.com/problemset/problem/597/C 1900
https://codeforces.com/problemset/problem/961/E 1900（不止一种做法）
区间元素去重后的异或和 https://codeforces.com/problemset/problem/703/D 2100
- 联系 https://www.luogu.com.cn/problem/P1972
建模 https://
    
func _(n int) {
	tree := make([]int, n+1) // int
	add := func(i, val int) {
		for ; i < len(tree); i += i & -i {
			tree[i] += val
		}
	}
	sum := func(i int) (res int) {
		for ; i > 0; i &= i - 1 {
			res += tree[i]
		}
		return
	}
	query := func(l, r int) int { return sum(r) - sum(l-1) } // [l,r]

	// 差分树状数组，可用于区间更新+单点查询 queryOne(i) = a[i] + sum(i) // a 从 1 开始
	// r+1 即使超过 n 也没关系，因为不会用到
	// 模板题 https://www.luogu.com.cn/problem/P3368
	addRange := func(l, r, val int) { add(l, val); add(r+1, -val) } // [l,r]

	// 求权值树状数组第 k 小的数（k > 0）
	// 这里 tree[i] 表示 i 的个数
	// 返回最小的 x 满足 ∑i=[1..x] tree[i] >= k
	// 思路类似倍增的查询，不断寻找 ∑<k 的数，最后 +1 就是答案
	// https://oi-wiki.org/ds/fenwick/#tricks
	//
	// https://codeforces.com/blog/entry/61364
	// https://codeforces.com/problemset/problem/1404/C
	// todo https://codeforces.com/contest/992/problem/E
	// https://atcoder.jp/contests/abc287/tasks/abc287_g
	// 二分 https://www.luogu.com.cn/problem/P4137
	// - 代码见下面的 rangeMex
	kth := func(k int) (res int) {
		const log = 17 // bits.Len(uint(n))
		for b := 1 << (log - 1); b > 0; b >>= 1 {
			if next := res | b; next < len(tree) && k > tree[next] {
				k -= tree[next]
				res = next
			}
		}
		return res + 1
	}

	// 输出权值树状数组的 mex（这里的定义是第一个没出现的正数）
	// 注意不能有重复元素
	mex := func() (res int) {
		const log = 17 // bits.Len(uint(n))
		for b := 1 << (log - 1); b > 0; b >>= 1 {
			if next := res | b; tree[next] == next {
				res = next
			}
		}
		res++ // mex
		return
	}

	// 常数优化：O(n) 建树
	// https://oi-wiki.org/ds/fenwick/#tricks
	init := func(a []int) { // len(tree) = len(a) + 1
		for i, v := range a {
			i++
			tree[i] += v
			if j := i + i&-i; j < len(tree) {
				tree[j] += tree[i]
			}
		}
	}

	// a 的下标从 1 开始
	initFrom := func(a []int) {
		for i := 1; i < len(a); i++ {
			if j := i + i&-i; j < len(a) {
				a[j] += a[i]
			}
		}
		tree = a
	}

	// 另外一种写法（效率和算两次一样）
	// https://www.luogu.com.cn/blog/countercurrent-time/qian-tan-shu-zhuang-shuo-zu-you-hua
	query = func(l, r int) (s int) {
		if l > r {
			panic(9)
		}
		l--
		for ; r > l; r &= r - 1 {
			s += tree[r]
		}
		for ; l > r; l &= l - 1 {
			s -= tree[l]
		}
		return
	}

	{
		// 时间戳优化（通常用于多组数据+值域树状数组）https://oi-wiki.org/ds/fenwick/#%E6%97%B6%E9%97%B4%E6%88%B3%E4%BC%98%E5%8C%96
		// https://codeforces.com/problemset/submission/1801/205042964
		const mx int = 1e6
		tree := [mx + 1]int{} // 默认都是 0
		time := [mx + 1]int{}
		curCase := 1 // 从 1 开始
		upd := func(i int, v int) {
			for ; i <= mx; i += i & -i {
				if time[i] != curCase {
					time[i] = curCase
					tree[i] = 0 // reset
				}
				tree[i] += v
			}
		}
		pre := func(i int) (res int) {
			for ; i > 0; i &= i - 1 {
				if time[i] == curCase {
					res += tree[i]
				} // 否则，相当于 res += 0
			}
			return
		}
		_, _ = upd, pre
	}

	// 求逆序对的方法之一
	// 如果 a 范围较大则需要离散化（但这样还不如直接用归并排序）
	// 归并做法见 misc.go 中的 mergeCount
	// 扩展 https://codeforces.com/problemset/problem/362/C 1900
	// 环形最小逆序对 https://www.luogu.com.cn/problem/solution/P2995
	// todo 扩展：某些位置上的数待定时的逆序对的期望值 https://codeforces.com/problemset/problem/1096/F
	// https://codeforces.com/problemset/problem/1585/D 1900
	// https://codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/A
	// 逆序对的奇偶性 https://www.luogu.com.cn/blog/203623/sol-p3760-tjoi2017-yi-huo-hu
	// - https://ac.nowcoder.com/acm/contest/308/D
	// todo https://codeforces.com/problemset/problem/911/D
	//  https://codeforces.com/contest/987/problem/E
	//  https://atcoder.jp/contests/chokudai_S001/tasks/chokudai_S001_l
	//  https://atcoder.jp/contests/abc296/tasks/abc296_f
	//  https://atcoder.jp/contests/arc136/tasks/arc136_b
	//  https://www.codechef.com/problems/DYNAINV?tab=statement
	//  https://ac.nowcoder.com/acm/problem/20861
	// 1e9 范围逆序对 https://codeforces.com/problemset/problem/540/E
	// 三元逆序对 https://codeforces.com/problemset/problem/61/E
	cntInversions := func(a []int) int {
		n := len(a)
		tree := make([]int, n+1)
		add := func(i int) {
			for ; i <= n; i += i & -i {
				tree[i]++
			}
		}
		sum := func(i int) (res int) {
			for ; i > 0; i &= i - 1 {
				res += tree[i]
			}
			return
		}
		invCnt := 0
		for i, v := range a {
			// 由于 i 从 0 开始算，这里先 sum 后 add
			invCnt += i - sum(v)
			add(v)
		}
		return invCnt
	}

	// 通过邻项交换，把数组 a 变成数组 b，需要的最小操作次数
	// 如果无法做到，返回 -1
	// https://atcoder.jp/contests/arc120/tasks/arc120_c
	// LC1850 https://leetcode.cn/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number/ 2073
	minSwap := func(a, b []int) (res int) {
		tree := make([]int, len(a)+1)
		add := func(i int) {
			for i++; i < len(tree); i += i & -i {
				tree[i]++
			}
		}
		sum := func(i int) (res int) {
			for ; i > 0; i &= i - 1 {
				res += tree[i]
			}
			return
		}

		pos := map[int][]int{}
		for i, v := range a {
			pos[v] = append(pos[v], i)
		}
		for i, v := range b {
			p := pos[v]
			if len(p) == 0 {
				return -1
			}
			j := p[0]
			pos[v] = p[1:]
			res += i - sum(j)
			add(j)
		}
		return
	}

	_ = []interface{}{add, sum, query, addRange, kth, mex, init, initFrom, cntInversions, minSwap}
}