问题：
给定一个数字m，则有一个数组Array：1～m分别在数组的0～m-1位上放置。
在给定一个操作对象数组 queries，表示操作对象数字，
返回当前该数字的位置到结果数组res中，并将该数字移到Array数组开头。
求操作完所有queries中的对象后，得到的res。
Example 1: Input: queries = [3,1,2,1], m = 5 Output: [2,1,2,1] Explanation: The queries are processed as follow: For i=0: queries[i]=3, P=[1,2,3,4,5], position of 3 in P is 2, then we move 3 to the beginning of P resulting in P=[3,1,2,4,5]. For i=1: queries[i]=1, P=[3,1,2,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,3,2,4,5]. For i=2: queries[i]=2, P=[1,3,2,4,5], position of 2 in P is 2, then we move 2 to the beginning of P resulting in P=[2,1,3,4,5]. For i=3: queries[i]=1, P=[2,1,3,4,5], position of 1 in P is 1, then we move 1 to the beginning of P resulting in P=[1,2,3,4,5]. Therefore, the array containing the result is [2,1,2,1]. Example 2: Input: queries = [4,1,2,2], m = 4 Output: [3,1,2,0] Example 3: Input: queries = [7,5,5,8,3], m = 8 Output: [6,5,0,7,5] Constraints: 1 <= m <= 10^3 1 <= queries.length <= m 1 <= queries[i] <= m
解法：
Constraints: 1 <= m <= 10^3
则可说明，该问题满足 m*m 的时间复杂度
leetcode允许运行时间10^6
解法一：
position记录法，
完全按照题意，进行操作，
只是使用pos数组记录每个数字的位置。（hash方便查找）
pos[q]=j 代表数字 q 所在的位置在 j 上。
那么queries中的每一个数字 i 即能瞬间找到其对应位置pos[q]。
找到后，res.push_back(pos[q])
同时对1～m的所有数字的位置进行更新：
1.pos[i] < pos[q] ：都往后移动一位：pos[i]++
2.pos[q]=0：把q移动到首位。
代码参考：
1 class Solution { 2 public: 3 vector<int> processQueries(vector<int>& queries, int m) { 4 vector<int> pos(m+1); 5 vector<int> res; 6 iota(pos.begin(), pos.end(), -1);//从pos[0]=-1开始，pos[i]=(pos[i-1]++); 7 for(int q:queries){ 8 res.push_back(pos[q]); 9 for(int i=1; i<=m; i++){ 10 if(pos[i]<pos[q]) pos[i]++; 11 } 12 pos[q]=0; 13 } 14 return res; 15 } 16 };
解法二：
Fenwick Tree方法：
Fenwick Tree介绍：https://zxi.mytechroad.com/blog/sp/fenwick-tree-binary-indexed-tree-sp3/
【转自：花花酱 的博客，地址如上】
一般对应问题：
求数组前缀和（query方法）。（且中间含有多次，单独更新（update方法）其中某个值的操作）
解法思想：存储连续多个元素之和->使得所求=多个既存连续组之和。（空间换时间）
选择元素和的根据：Tree->使得时间复杂度为： log n
选择方法：
- partsum[1]=元素1的值=1 【1】
- partsum[2]=元素1+元素2的值=1+2=3 【1-2】
- partsum[3]=元素3的值=3 【3】
- partsum[4]=partsum[2]+partsum[3]+元素4的值=1+2+3+4=6+4=10 【1-4】
- ……
那么当我们要求前3个数之和的时候，
我们要用【3】+【1-2】= partsum[3]+partsum[2]=3+3=6
要得到上述的Tree，使用lowbit方法进行构建：
对要更新的数，取二进制，对该数+=该数的（为1的）最低位，都进行更新。如要更新1，则需更新1(1)，2(10)，4(100)，8(1000)...直到最后一个数。
求和，则对该数取二进制，累加：对该数-=该数的（为1的）最低位。如要求7，则累加7(111)+6(110)+4(100)
对于本问题：
由于FenwickTree能将变动一个元素，并查找前缀累计的问题，时间复杂度转为log n
那么，我们可以将本问题，转化为：
在给定数组前面再预留queries.size的空位，用来插入所要插入的数字，
插入后，将该数字原来的位置置空即可。其他数字位置不变。
因为要求指定数字的位置，要联系到前缀和，那么我们将存在数字的位置置为1，前缀和，即为该数字目前的位置。
另外，同样我们为了快速定位数字位置，引入pos[]的hash用来记录位置。
下图的
每一行，代表queries中的一次操作。
每一个cell
如第8位-> 3:1 其中3表示数字，并不实际存在tree中，后面的1才是我们要存在tree中的内容。
而pos[3]=8来确定3所在的位置。
代码参考：
1 class FenwickTree { 2 private: 3 vector<int> partSum; 4 int lowest1bit(int num){ 5 return num & (-num); 6 //-num = ~num+1 7 //e.g. num=5 (0110) -> -num = -5 = ~(0110)+1 = 1001 +1 = 1010 8 // num & (-num) = 0110 & 1010 = 0010 9 } 10 public: 11 FenwickTree(int n):partSum(n+1,0) {} 12 //update all the item in the partition Sum route of i 13 void update(int i, int val){ 14 while(i<partSum.size()){ 15 partSum[i]+=val; 16 i+=lowest1bit(i); 17 } 18 } 19 //find Sum(0~i) 20 int query(int i){ 21 int sum=0; 22 while(i>0){ 23 sum+=partSum[i]; 24 i-=lowest1bit(i); 25 } 26 return sum; 27 } 28 }; 29 30 class Solution { 31 public: 32 vector<int> processQueries(vector<int>& queries, int m) { 33 vector<int> pos(m+1); 34 vector<int> res; 35 int qsize=queries.size(); 36 FenwickTree tree(m+qsize+1); 37 for(int i=1; i<=m; i++){ 38 pos[i]=qsize+i; 39 tree.update(pos[i],1); 40 } 41 42 for(int q:queries){ 43 res.push_back(tree.query(pos[q]-1)); 44 tree.update(pos[q],-1); 45 pos[q]=qsize; 46 tree.update(qsize,1); 47 qsize--; 48 } 49 return res; 50 } 51 };