树状数组(Binary Indexed Tree(BIT), Fenwick Tree) 是一个查询和修改复杂度都为 $O(\log n)$ 的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；
经过简单修改可以在 $O(\log n)$ 的复杂度下进行范围修改，但是这时只能查询其中一个元素的值。
NOIP 2007提高组试题1。
某次科研调查时得到了 $n$ 个自然数，每个数均不超过 $1500000000(1.5 \times 10^9)$。已知不相同的数不超过 $10000$ 个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。
输入文件包含 $n + 1$ 行：
第 $1$ 行是整数 $n$，表示自然数的个数。
第 $2$ ~ $n+1$ 行每行一个自然数。
输出文件包含 $m$ 行（$m$ 为 $n$ 个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。
NOIP 2006 普及组试题1。
明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 $N$ 个 $1$ 到 $1000$ 之间的随机整数（$N \leq 100$），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成去重与排序的工作。
输入文件有 $2$ 行:
第 $1$ 行为 $1$ 个正整数，表示所生成的随机数的个数：$N$
第 $2$ 行有 $N$ 个用空格隔开的正整数，为所产生的随机数。
输出文件也是 $2$ 行：
第 $1$ 行为 $1$ 个正整数 $M$，表示不相同的随机数的个数。
第 $2$ 行为 $M$ 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。
军方截获的信息由 $N(1 \leq N \leq 30000)$ 个整数组成，因为是敌国的高端秘密，所以一时不能破获。最原始的想法就是对这 $N$ 个整数进行小到大排序。排序后每个数都对应一个序号，然后对第 $i$ 个是什么数感兴趣，现在要求编程完成。
第一行整数 $N$。
第二行是 $N$ 个截获的数字，相邻数字由一个空格隔开。
第三行是一个数字 $K (1 \leq K \leq N)$。
从第四行开始，共有 $K$ 个排序后的序号 $X_1, X_2, X_3, \cdots X_k$，每行一个。
输出数据有 $K$ 行，每行一个整数。这个整数就是每个序号 $X_i$ 对应的数。
Update your browser to view this website correctly. Update my browser now