一维数组

一维数组的 CRUD

有关数组的 CRUD 其实是非常简单的。

// 顺序表的.h 文件
#include<iostream>
using namespace std;
const int MAXSIZE = 20;
class SqList{
private:
    int *data;
    int length;
public:
    SqList();  // 构造函数
    ~SqList(); // 析构函数
    void CreatList(int a[], int n); // 创建顺序表
    void Display();  // 输出顺序表中所有元素
    int GetLength(); // 获取顺序表的长度
    bool GetElem(int, int &elem); // 获取顺序表中的某个元素
    bool ListInsert(int i, int elem); // 插入元素
    bool ListDelete(int i, int &elem); // 删除元素
};

SqList::SqList(){
    cout<<"constract ok"<<endl;
    data = new int[MAXSIZE];
    length = 0;
}

SqList::~SqList(){
    cout<<"No"<<endl;
    delete [] data;}

void SqList::CreatList(int a[], int n){for(int i = 0; i < n; i++){data[i] = a[i];
    }
    length = n;
    cout<<"create SqList success!"<<endl;
}

// 获取顺序表的长度
int SqList::GetLength(){return length;}

// 获取指定元素
bool SqList::GetElem(int i, int &e){if(length == 0 || i < 1 || i > length){return false;}
    e = data[i-1];
    return true;
}

// 插入元素
bool SqList::ListInsert(int i, int e){if(length == MAXSIZE) // 保证插入位置正确
        return false;
    if(i < 1 || i > length+1)
        return false;
    if(i < length){for(int k = length-1; k >= i-1; k--)  // 将插入位置之后的元素都向后移动一个位置
            data[k+1] = data[k];
    }
    data[i-1] = e;  // 将待插入的元素赋值给插入位置
    length++;  // 将顺序表的长度增加一个
    return true;
}

// 删除元素
bool SqList::ListDelete(int i, int &e){if(length == 0)  // 保证删除位置正确
        return false;
    if(i < 1 || i > length)
        return false;
    e = data[i-1];  // 将要删除的元素保存给 e
    if(i < length){for(int k = i; k < length; k++){ // 将删除位置后面的元素都向前移动一个位置
            data[k-1] = data[k];
        }
    }
    length--;  // 将顺序表的长度删除一个
    return true;
}

void SqList::Display(){
    cout<<"display SqList:";
    for(int i = 0; i < length; i++){cout<<data[i]<<"\t";
    }
    cout<<endl;
}

数组排序

https://www.cnblogs.com/still…

冒泡法

基本思想是:两两比较相邻记录的关键字, 如果反序则交换

冒泡排序时间复杂度最好的情况为 O(n), 最坏的情况是 O(n^2)

改进思路 1：设置标志位，明显如果有一趟没有发生交换（flag = false)，说明排序已经完成

改进思路 2：记录一轮下来标记的最后位置，下次从头部遍历到这个位置就 Ok

选择排序

通过 n - i 次关键字之间的比较, 从 n -i+1 个记录中选择关键字最小的记录, 并和第 i(1<=i<=n)个记录交换之

尽管与冒泡排序同为 O(n^2), 但简单选择排序的性能要略优于冒泡排序

插入排序

将一个记录插入到已经排好序的有序表中, 从而得到一个新的, 记录数增 1 的有序表

时间复杂度也为 O(n^2), 比冒泡法和选择排序的性能要更好一些

希尔排序

先将整个待排元素序列分割成若干子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排

序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（增量为 1）。其时间复杂度为 O(n^3/2), 要好于直接

插入排序的 O(n^2)

归并排序

假设初始序列含有 n 个记录, 则可以看成 n 个有序的子序列, 每个子序列的长度为 1, 然后两两归并, 得到 (不小于 n / 2 的最小整数) 个长度为 2

或 1 的有序子序列, 再两两归并,… 如此重复, 直至得到一个长度为 n 的有序序列为止, 这种排序方法称为 2 路归并排序。时间复杂度为

O(nlogn), 空间复杂度为 O(n+logn), 如果非递归实现归并, 则避免了递归时深度为 logn 的栈空间 空间复杂度为 O(n)

快速排序

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。时间复杂度为 O(nlogn)

堆排序

（见后）

总结

Code

#include<iostream>
using namespace std;

void swap1(int *left, int *right)
{
    int temp = *left;
    *left = *right;
    *right = temp;
}

void swap2(int &left, int &right)
{
    int temp = left;
    left = right;
    right = left;
}

void swap3(int &left, int &right)
{if (&left != &right) 
    {
        left ^= right;
        right ^= left;
        left ^= right;
    }
}

/*****************************************************************/
/* 冒泡排序时间复杂度最好的情况为 O(n), 最坏的情况是 O(n^2)
* 基本思想是: 两两比较相邻记录的关键字, 如果反序则交换 */

void BubbleSort1(int arr[], int num)
{
    int i, j;
    for (i = 0; i < num; i++)
    {for (j = 1; j < num - i; j++)
        {if (arr[j - 1] > arr[j])
                swap1(&arr[j - 1], &arr[j]);
        }
    }
}

// 改进思路：设置标志位，明显如果有一趟没有发生交换（flag = flase)，说明排序已经完成.
void BubbleSort2(int arr[], int num)
{
    int k = num;
    int j;
    bool flag = true;
    while (flag)
    {
        flag = false;
        for (j = 1; j < k; j++)
        {if (arr[j - 1] > arr[j])
            {swap1(&arr[j - 1], &arr[j]);
                flag = true;
            }
        }
        k--;
    }
}
// 改进思路：记录一轮下来标记的最后位置，下次从头部遍历到这个位置就 Ok
void BubbleSort3(int arr[], int num)
{
    int k, j;
    int flag = num;
    while (flag > 0)
    {
        k = flag;
        flag = 0;
        for (j = 1; j < k; j++)
        {if (arr[j - 1] > arr[j])
            {swap1(&arr[j - 1], &arr[j]);
                flag = j;
            }
        }
    }
}
/*************************************************************************/

/**************************************************************************/
/* 插入排序: 将一个记录插入到已经排好序的有序表中, 从而得到一个新的, 记录数增 1 的有序表
* 时间复杂度也为 O(n^2), 比冒泡法和选择排序的性能要更好一些 */

void InsertionSort(int arr[], int num)
{
    int temp;
    int i, j;
    for (i = 1; i < num; i++)
    {temp = arr[i];
        for (j = i; j > 0 && arr[j - 1] > temp; j--)
            arr[j] = arr[j - 1];
        arr[j] = temp;
    }
}

/****************************************************************************/

/* 希尔排序: 先将整个待排元素序列分割成若干子序列（由相隔某个“增量”的元素组成的）分别进行
直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（增量为 1）。其时间复杂度为 O(n^3/2), 要好于直接插入排序的 O(n^2) */
void ShellSort(int *arr, int N)
{
    int i, j, increment;
    int tmp;
    for (increment = N / 2; increment > 0; increment /= 2)
    {for (i = increment; i < N; i++)
        {tmp = arr[i];
            for (j = i; j >= increment; j -= increment)
            {if (arr[j - increment] > tmp)
                    arr[j] = arr[j - increment];
                else
                    break;
            }
            arr[j] = tmp;
        }

    }
}

/**************************************************************************/

/* 简单选择排序(simple selection sort) 就是通过 n - i 次关键字之间的比较, 从 n -i+1
* 个记录中选择关键字最小的记录, 并和第 i(1<=i<=n)个记录交换之
* 尽管与冒泡排序同为 O(n^2), 但简单选择排序的性能要略优于冒泡排序 */

void SelectSort(int arr[], int num)
{
    int i, j, Mindex;
    for (i = 0; i < num; i++)
    {
        Mindex = i;
        for (j = i + 1; j < num; j++)
        {if (arr[j] < arr[Mindex])
                Mindex = j;
        }

        swap1(&arr[i], &arr[Mindex]);
    }
}

/********************************************************************************/
/* 假设初始序列含有 n 个记录, 则可以看成 n 个有序的子序列, 每个子序列的长度为 1, 然后
* 两两归并, 得到 (不小于 n / 2 的最小整数) 个长度为 2 或 1 的有序子序列, 再两两归并,...
* 如此重复, 直至得到一个长度为 n 的有序序列为止, 这种排序方法称为 2 路归并排序
* 时间复杂度为 O(nlogn), 空间复杂度为 O(n+logn), 如果非递归实现归并, 则避免了递归时深度为 logn 的栈空间
* 空间复杂度为 O(n) */


/*lpos is the start of left half, rpos is the start of right half*/
void merge(int a[], int tmp_array[], int lpos, int rpos, int rightn)
{
    int i, leftn, num_elements, tmpos;

    leftn = rpos - 1;
    tmpos = lpos;
    num_elements = rightn - lpos + 1;

    /*main loop*/
    while (lpos <= leftn && rpos <= rightn)
        if (a[lpos] <= a[rpos])
            tmp_array[tmpos++] = a[lpos++];
        else
            tmp_array[tmpos++] = a[rpos++];

    while (lpos <= leftn) /*copy rest of the first part*/
        tmp_array[tmpos++] = a[lpos++];
    while (rpos <= rightn) /*copy rest of the second part*/
        tmp_array[tmpos++] = a[rpos++];

    /*copy array back*/
    for (i = 0; i < num_elements; i++, rightn--)
        a[rightn] = tmp_array[rightn];
}


void msort(int a[], int tmp_array[], int left, int right)
{
    int center;

    if (left < right)
    {center = (right + left) / 2;
        msort(a, tmp_array, left, center);
        msort(a, tmp_array, center + 1, right);
        merge(a, tmp_array, left, center + 1, right);
    }
}



void merge_sort(int a[], int n)
{
    int *tmp_array;
    tmp_array = (int *)malloc(n * sizeof(int));

    if (tmp_array != NULL)
    {msort(a, tmp_array, 0, n - 1);
        free(tmp_array);
    }

    else
        printf("No space for tmp array!\n");
}

/************************************************************************************/
/* 堆是具有下列性质的完全二叉树: 每个节点的值都大于或等于其左右孩子节点的值, 称为大顶堆；* 或者每个节点的值都小于或等于其左右孩子节点的值, 称为小顶堆 */

/* 堆排序就是利用堆进行排序的方法. 基本思想是: 将待排序的序列构造成一个大顶堆. 此时, 整个序列的最大值就是堆顶
* 的根结点. 将它移走(其实就是将其与堆数组的末尾元素交换, 此时末尾元素就是最大值), 然后将剩余的 n - 1 个序列重新
* 构造成一个堆, 这样就会得到 n 个元素的次大值. 如此反复执行, 便能得到一个有序序列了
*/
/* 时间复杂度为 O(nlogn), 好于冒泡, 简单选择, 直接插入的 O(n^2) */

// 构造大顶堆
#define leftChild(i) (2*(i) + 1)

void percDown(int *arr, int i, int N)
{
    int tmp, child;
    for (tmp = arr[i]; leftChild(i) < N; i = child)
    {child = leftChild(i);
        if (child != N - 1 && arr[child + 1] > arr[child])
            child++;
        if (arr[child] > tmp)
            arr[i] = arr[child];
        else
            break;
    }
    arr[i] = tmp;
}

void HeapSort(int *arr, int N)
{
    int i;
    for (i = N / 2; i >= 0; i--)
        percDown(arr, i, N);
    for (i = N - 1; i > 0; i--)
    {swap1(&arr[0], &arr[i]);
        percDown(arr, 0, i);
    }
}

树状数组（BIT）

https://www.cnblogs.com/xenny…

概念

在此之前要强调一下 BIT 的功能：可以解决大部分基于区间上的更新以及求和问题。

lowbit(x) = x & (-x) = 2^k

利用的负数的存储特性，负数是以补码存储的，对于整数运算 x&(-x)有

● 当 x 为 0 时，即 0 & 0，结果为 0；●当 x 为奇数时，最后一个比特位为 1，取反加 1 没有进位，故 x 和 - x 除最后一位外前面的位正好相反，按位与结果为 0。结果为 1。●当 x 为偶数，且为 2 的 m 次方时，x 的二进制表示中只有一位是 1（从右往左的第 m + 1 位），其右边有 m 位 0，故 x 取反加 1 后，从右到左第有 m 个 0，第 m + 1 位及其左边全是 1。这样，x& (-x) 得到的就是 x。●当 x 为偶数，却不为 2 的 m 次方的形式时，可以写作 x = y * (2^k)。其中，y 的最低位为 1。实际上就是把 x 用一个奇数左移 k 位来表示。这时，x 的二进制表示最右边有 k 个 0，从右往左第 k + 1 位为 1。当对 x 取反时，最右边的 k 位 0 变成 1，第 k + 1 位变为 0；再加 1，最右边的 k 位就又变成了 0，第 k + 1 位因为进位的关系变成了 1。左边的位因为没有进位，正好和 x 原来对应的位上的值相反。二者按位与，得到：第 k + 1 位上为 1，左边右边都为 0。结果为 2^k。总结一下：x&(-x)，当 x 为 0 时结果为 0；x 为奇数时，结果为 1；x 为偶数时，结果为 x 中 2 的最大次方的因子。

而且这个有一个专门的称呼，叫做 lowbit，即取 2^k。

树状数组

黑色数组代表原来的数组（下面用 A[i]代替），红色结构代表我们的树状数组 (下面用 C[i] 代替)，发现没有，每个位置只有一个方框，令每个位置存的就是子节点的值的和，则有

• C[1] = A[1];
• C[2] = A[1] + A[2];
• C[3] = A[3];
• C[4] = A[1] + A[2] + A[3] + A[4];
• C[5] = A[5];
• C[6] = A[5] + A[6];
• C[7] = A[7];
• C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];

可以发现，这颗树是有规律的

$$
C[i] = A[i-2^{k}+1]+ A[i-2^{k}+2] + …+A[i] 其中 k 为 i 的二进制中从最低位到高位连续零的长度
$$

例如 i = 8(1000)时候，k = 3，可自行验证。

这个怎么实现求和呢，比如我们要找前 7 项和，那么应该是 SUM = C[7] + C[6] + C[4];

而根据上面的式子，容易的出

$$
SUM_{i} = C[i]+ C[i-2^{k1}] + C[(i-2^{k1})-2^{k2}]+\dots
$$

其实树状数组就是一个二进制上面的应用。

现在新的问题来了 2^k 该怎么求呢，之前已经提到过 lowbit 运算。

现在又有一个新问题：如何知道 A[1]+A[2]+…+A[i] 对应 C 中的哪些项之和呢？

$$
记 {\color{Red} SUM(1,x)=A[1]+…+A[x]} , 由于 C[x] 的覆盖长度是 lowbit(x)
所以{\color{Red} C[x]=A[A-lowbit(x)+1]+…A[x]}
$$

$$
{\color{Red} \therefore SUM(1,x)=A[1]+…+A[x]=A[1]+…+A[x-lowbit(x)]+A[x-lowbit(x)+1]+…+A[x]=SUM(1,x-lowbit(x))+C[x]}
$$

Code

int n;
int a[1005],c[1005]; // 对应原数组和树状数组

int lowbit(int x){return x&(-x);
}

void updata(int i,int k){    // 在 i 位置加上 k
    while(i <= n){c[i] += k;
        i += lowbit(i);
    }
}

int getsum(int i){// 求 A[1 - i]的和
    int res = 0;
    while(i > 0){res += c[i];
        i -= lowbit(i);
    }
    return res;
}
// 两种 getsum 都可以
int getSum(int x){
    int sum = 0;
    for(int i = x; i > 0; i -= lowbit(i)){sum += c[i];
    }
    return sum;
}
//updata 函数将第 x 个整数加上 v
void upData(int x, int v){for(int i = x; i <= N; i += lowbit(i)){//i 必须取到 N，N 为元素个数.
        c[i] += x; // 让 C[i]加上 v，然后让 C[i+lowbit(i)]+v
    }
}

变形

单点更新，单点查询

传统数组即可。

单点更新，区间查询

问题描述：

C 国的死对头 A 国这段时间正在进行军事演习，所以 C 国间谍头子 Derek 和他手下 Tidy 又开始忙乎了。A 国在海岸线沿直线布置了 N 个工兵营地,Derek 和 Tidy 的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数 C 国都掌握的一清二楚, 每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手, 但这些都逃不过 C 国的监视。
中央情报局要研究敌人究竟演习什么战术, 所以 Tidy 要随时向 Derek 汇报某一段连续的工兵营地一共有多少人, 例如 Derek 问:“Tidy, 马上汇报第 3 个营地到第 10 个营地共有多少人!”Tidy 就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而 Derek 每次询问的段都不一样，所以 Tidy 不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek 对 Tidy 的计算速度越来越不满:” 你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy 想：“你自己来算算看，这可真是一项累人的工作! 我恨不得你炒我鱿鱼呢!”无奈之下，Tidy 只好打电话向计算机专家 Windbreaker 求救,Windbreaker 说：“死肥仔，叫你平时做多点 acm 题和看多点算法书，现在尝到苦果了吧!”Tidy 说：” 我知错了。。。” 但 Windbreaker 已经挂掉电话了。Tidy 很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy 还是会受到 Derek 的责骂的.

Input

第一行一个整数 T，表示有 T 组数据。
每组数据第一行一个正整数 N（N<=50000）, 表示敌人有 N 个工兵营地，接下来有 N 个正整数, 第 i 个正整数 ai 代表第 i 个工兵营地里开始时有 ai 个人（1<=ai<=50）。
接下来每行有一条命令，命令有 4 种形式：
(1) Add i j,i 和 j 为正整数, 表示第 i 个营地增加 j 个人（j 不超过 30）
(2)Sub i j ,i 和 j 为正整数, 表示第 i 个营地减少 j 个人（j 不超过 30）;
(3)Query i j ,i 和 j 为正整数,i<=j，表示询问第 i 到第 j 个营地的总人数;
(4)End 表示结束，这条命令在每组数据最后出现;
每组数据最多有 40000 条命令

Output

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End 

Case

6
33
59

Code

#include <bits/stdc++.h>
using namespace std;

int n,m;
int a[50005],c[50005]; // 对应原数组和树状数组

int lowbit(int x){return x&(-x);
}

void updata(int i,int k){    // 在 i 位置加上 k
    while(i <= n){c[i] += k;
        i += lowbit(i);
    }
}

int getsum(int i){// 求 A[1 - i]的和
    int res = 0;
    while(i > 0){res += c[i];
        i -= lowbit(i);
    }
    return res;
}

int main(){
    int t;
    cin>>t;
    for(int tot = 1; tot <= t; tot++){
        cout << "Case" << tot << ":" << endl;
        memset(a, 0, sizeof a);
        memset(c, 0, sizeof c);
        cin>>n;
        for(int i = 1; i <= n; i++){cin>>a[i];
            updata(i,a[i]);   // 输入初值的时候，也相当于更新了值
        }

        string s;
        int x,y;
        while(cin>>s && s[0] != 'E'){
            cin>>x>>y;
            if(s[0] == 'Q'){    // 求和操作
                int sum = getsum(y) - getsum(x-1);    //x- y 区间和也就等于 1 - y 区间和减去 1 -(x-1)区间和
                cout << sum << endl;
            }
            else if(s[0] == 'A'){updata(x,y);
            }
            else if(s[0] == 'S'){updata(x,-y);    // 减去操作，即为加上相反数
            }
        }

    }
    return 0;
}

区间更新，单点查询

如果题目是让你把 x - y 区间内的所有值全部加上 k 或者减去 k，然后查询操作是问某个点的值，这种时候该怎么做呢。如果是像上面的树状数组来说，就必须把 x - y 区间内每个值都更新，这样的复杂度肯定是不行的，这个时候，就不能再用数据的值建树了，这里我们引入差分，利用差分建树。

假设我们规定 A[0] = 0;

$$
A[i] = {\textstyle \sum_{j=1}^{i}}D[j];(其中 D[j] = A[j]-A[j-1])
$$

即前面 i 项的差值和，这个有什么用呢？例如对于下面这个数组

• A[] = 1 2 3 5 6 9
• D[] = 1 1 1 2 1 3

如果我们把 [2,5] 区间内值加上 2，则变成了

• A[] = 1 4 5 7 8 9
• D[] = 1 3 1 2 1 1

发现了没有，当某个区间 [x,y] 值改变了，区间内的差值是不变的，只有 D[x]和 D[y+1]的值发生改变

Code

int n,m;
int a[50005] = {0},c[50005]; // 对应原数组和树状数组

int lowbit(int x){return x&(-x);
}

 void updata(int i,int k){    // 在 i 位置加上 k
     while(i <= n){c[i] += k;
        i += lowbit(i);
    }
}

int getsum(int i){// 求 D[1 - i]的和，即 A[i]值
    int res = 0;
  while(i > 0){res += c[i];
       i -= lowbit(i);
   }
   return res;
}

int main(){cin>>n;27     for(int i = 1; i <= n; i++){cin>>a[i];
       updata(i,a[i] - a[i-1]);   // 输入初值的时候，也相当于更新了值
  }
   
   //[x,y]区间内加上 k
   updata(x,k);    //A[x] - A[x-1]增加 k
    updata(y+1,-k);        //A[y+1] - A[y]减少 k
    
    // 查询 i 位置的值
    int sum = getsum(i);

    return 0;
}

区间查询，区间查询

上面我们说的差值建树状数组，得到的是某个点的值，那如果我既要区间更新，又要区间查询怎么办。这里我们还是利用差分，由上面可知

$$
{\textstyle \sum_{i=1}^{n}}A[i]= {\textstyle \sum_{i=1}^{n}} {\textstyle \sum_{j=1}^{i}D[j]}
$$

$$
A[1]+A[2]+…+A[n]=(D[1])+(D[1]+D[2])+…+(D[1]+D[2]+…+D[n])=n\times (D[1]+D[2]+…+D[n])-(0\times D[1]+1\times D[2]+…+(n-1)\times D[n])
$$

所以上式可以变为：

$$
{\textstyle \sum_{i=1}^{n}}A[i]=n\times {\textstyle \sum_{i}^{n}}=D[i]- {\textstyle \sum_{i=1}^{n}}(D[i]\times (i-1))
$$

Code

int n,m;
int a[50005] = {0};
int sum1[50005];    //(D[1] + D[2] + ... + D[n])
int sum2[50005];    //(1*D[1] + 2*D[2] + ... + n*D[n])

int lowbit(int x){return x&(-x);
}

void updata(int i,int k){
    int x = i;    // 因为 x 不变，所以得先保存 i 值
    while(i <= n){sum1[i] += k;
        sum2[i] += k * (x-1);
        i += lowbit(i);
    }
}

int getsum(int i){        // 求前缀和
    int res = 0, x = i;
    while(i > 0){res += x * sum1[i] - sum2[i];
        i -= lowbit(i);
    }
    return res;
}

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++){cin>>a[i];
        updata(i,a[i] - a[i-1]);   // 输入初值的时候，也相当于更新了值
    }

    //[x,y]区间内加上 k
    updata(x,k);    //A[x] - A[x-1]增加 k
    updata(y+1,-k);        //A[y+1] - A[y]减少 k

    // 求 [x,y] 区间和
    int sum = getsum(y) - getsum(x-1);

    return 0;
}

例题

题目 1 描述

给定一个有 N 个正整数的序列 A（N<=10^5，A[i]<=10^5），对序列中的每一个数，求出序列中它左边比它小的数的列数

题目 1 解释

{2，5，1，3，4} ,A[1] = 2; 在 A[1]左边比其小的数字有 0 个；A[2]=5，在 A[2]左边比其下的数字有 1 个；A[5]=4，在 A[5]左边比其小的数的个数为 3

Code 1

#include <ctdio>
#include <cstring>
const int maxn = 100010;
#define lowbit(i)  ((i)&(-i))
int C[maxn];  // 树状数组
void UpDate(int x, int v){for(int i = 0; i < maxn; i+= lowbit(i)){C[i] += v; // 让 C[i]+v 然后让 C[i+lowbit(i)]+v
    }
}
int GetSum(int x){
    int sum = 0;
    for(int i = x; i > 0; i -= lowbit(i)){sum += C[i];    // 累计 C[i], 然后把问题缩小为 SUM(1,i-lowbit(i))
    }
    return sum;
}
int main(){
    int n, x;
    scanf("%d",&n);
    memset(c, 0, sizeof(c));
    for(int i = 0; i < n; i++){scanf("%d",&x);
        update(x, 1);
        printf("%d\n", GetSum(x-1));
    }
    return 0;
}

本题是树状数组的最经典应用之一：统计序列中元素左边比该元素小的元素个数（小是题目定义）

扩展

离散化概念

若 A[i] <= N 不成立（eg：A[i] <= 10^9）, 好像树状数组没办法开那么大，时则不然。

其实 A{520,999999999,14,666,888888} 我们只需要考虑他们之间的大小关系即可，也就是说，这个 A 序列和 B{2 , 5 , 1 , 3 , 4}是等价的。{11，111，1，11}与{2，4, 1, 2}。需要做的是把 1~N 联系起来。

设置一个临时的结构体数组，用来存放输入序列元素的值以及原始序号，而在输入完成在之后将数组按照 val 从小到大排列，排序完成后按照“计算排名”的方式将排名“排名”根据原始序号 pos 存入一个新的数组即可。

Code

#include <ctdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int manx = 100010;
#define lowbit(i) ((i)&(-i))
struct Node {
    int val;
    int pos;
}temp[maxn];
int A[maxn];
int C[maxn];

void UpData(int x, int v){for(int i = 0; i < maxn; i += lowbit(i)){C[i] += v;
    } 
}
int GetSum(int x){
    int sum = 0; 
    for(int i = x; i > 0; i -= lowbit(i)){sum += C[i];
    }
    return sum;
}
bool cmp(Node a, Node b){return a.val < b.val;}
int main(){
    int n;
    scanf("%d",&n);
    memset(C, 0, sizeof(C));
    for(int i = 0; i < n; i++){scanf("%d",&temp[i].val);
        temp[i].pos = i;
    }
    sort(temp, temp + n, cmp);
    for(int i = 0; i < n; i++){if(i == 0 || temp[i].val != temp[i-1].val){A[temp[i].pos] = i + 1;// 必须从 1 开始
        }else{A[temp[i].pos] = A[temp[i-1].pos];
        }
    }
    for(int i = 0; i < n; i++){UpDate(A[i], 1);
        printf("%d\n",GetSum(A[i]-1));
    }
    return 0;
}

需要注意的是离散化的方法只能用于离线查询，也就是我已经知道所有元素的值之后才可以进行查询。如果是在线的查询，虽然也不是没有办法，记录数据然后离散化。

二维数组的树状数组

把 GetSum 和 UpDate 循环改成两重循环.

Code

若求 Aa 到 Ax 这个矩阵元素的元素之和 只需计算 GetSum(x,y)-GetSum(x-1,y)-GetSum(x,y-1)+GetSum(x-1,y-1)即可。

int C[maxn][maxn];

void UpDate(int x, int y, int v){for(int i = 0; i < maxn; i += lowbit(i)){for(int j = 0; j < maxn; i += lowbit(j)){C[i][j] += v;
        }
    }
}

int GetSum(int x, int y){
    int sum = 0;
    for(int i = 0; i > 0; i -= lowbit(i)){for(int j = 0; j > 0; j -= lowbit(i)){sum += C[i][j];
        }
    }
    return sum;
}

散列表（Hash）

https://blog.csdn.net/yyyljw/…

哈希表（Hash table，也叫散列表），是根据关键码值 (Key value) 而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

记录的存储位置 =f(关键字)

这里的对应关系 f 称为散列函数，又称为哈希（Hash 函数），采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。

哈希表 hashtable(key，value) 就是把 Key 通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将 value 存储在以该数字为下标的数组空间里。（或者：把任意长度的输入（又叫做预映射，pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。）

而当使用哈希表进行查询的时候，就是再次使用哈希函数将 key 转换为对应的数组下标，并定位到该空间获取 value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

数组的特点是：寻址容易，插入和删除困难；

而链表的特点是：寻址困难，插入和删除容易。

那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：

左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。

Hash 的应用

1、Hash 主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的 128 位的编码, 这些编码值叫做 Hash 值. 也可以说，Hash 就是找到一种数据内容和数据存放地址之间的映射关系。

2、查找：哈希表，又称为散列，是一种更加快捷的查找技术。我们之前的查找，都是这样一种思路：集合中拿出来一个元素，看看是否与我们要找的相等，如果不等，缩小范围，继续查找。而哈希表是完全另外一种思路：当我知道 key 值以后，我就可以直接计算出这个元素在集合中的位置，根本不需要一次又一次的查找！

举一个例子，假如我的数组 A 中，第 i 个元素里面装的 key 就是 i，那么数字 3 肯定是在第 3 个位置，数字 10 肯定是在第 10 个位置。哈希表就是利用利用这种基本的思想，建立一个从 key 到位置的函数，然后进行直接计算查找。

3、Hash 表在海量数据处理中有着广泛应用。

Hash Table 的查询速度非常的快，几乎是 O(1)的时间复杂度。

hash 就是找到一种数据内容和数据存放地址之间的映射关系。

散列法：元素特征转变为数组下标的方法。

我想大家都在想一个很严重的问题：“如果两个字符串在哈希表中对应的位置相同怎么办？”, 毕竟一个数组容量是有限的，这种可能性很大。解决该问题的方法很多，我首先想到的就是用“链表”。我遇到的很多算法都可以转化成链表来解决，只要在哈希表的每个入口挂一个链表，保存所有对应的字符串就 OK 了。

散列表的查找步骤
当存储记录时，通过散列函数计算出记录的散列地址
当查找记录时，我们通过同样的是散列函数计算记录的散列地址，并按此散列地址访问该记录

关键字——散列函数（哈希函数）——散列地址

优点：一对一的查找效率很高；

缺点：一个关键字可能对应多个散列地址；需要查找一个范围时，效果不好。

散列冲突：不同的关键字经过散列函数的计算得到了相同的散列地址。

好的散列函数 = 计算简单 + 分布均匀（计算得到的散列地址分布均匀）

哈希表是种数据结构，它可以提供快速的插入操作和查找操作。

优缺点

优点：不论哈希表中有多少数据，查找、插入、删除（有时包括删除）只需要接近常量的时间即 0(1）的时间级。实际上，这只需要几条机器指令。

哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要 O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。

如果不需要有序遍历数据，并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。

缺点：它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据（或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程）。

元素特征转变为数组下标的方法就是散列法。散列法当然不止一种，下面列出三种比较常用的：

1，除法散列法
最直观的一种，上图使用的就是这种散列法，公式：

  index = value % 16 

学过汇编的都知道，求模数其实是通过一个除法运算得到的，所以叫“除法散列法”。

2，平方散列法
求 index 是非常频繁的操作，而乘法的运算要比除法来得省时（对现在的 CPU 来说，估计我们感觉不出来），所以我们考虑把除法换成乘法和一个位移操作。公式：

  index = (value * value) >> 28（右移，除以 2^28。记法：左移变大，是乘。右移变小，是除。）

如果数值分配比较均匀的话这种方法能得到不错的结果，但我上面画的那个图的各个元素的值算出来的 index 都是 0——非常失败。也许你还有个问题，value 如果很大，value * value 不会溢出吗？答案是会的，但我们这个乘法不关心溢出，因为我们根本不是为了获取相乘结果，而是为了获取 index。

3，斐波那契（Fibonacci）散列法

平方散列法的缺点是显而易见的，所以我们能不能找出一个理想的乘数，而不是拿 value 本身当作乘数呢？答案是肯定的。

1，对于 16 位整数而言，这个乘数是 40503
2，对于 32 位整数而言，这个乘数是 2654435769
3，对于 64 位整数而言，这个乘数是 11400714819323198485

这几个“理想乘数”是如何得出来的呢？这跟一个法则有关，叫黄金分割法则，而描述黄金分割法则的最经典表达式无疑就是著名的斐波那契数列，即如此形式的序列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377, 610，987, 1597, 2584, 4181, 6765, 10946，…。另外，斐波那契数列的值和太阳系八大行星的轨道半径的比例出奇吻合。对我们常见的 32 位整数而言，公式：index = (value * 2654435769) >> 28

如果用这种斐波那契散列法的话，那上面的图就变成这样了：

注：用斐波那契散列法调整之后会比原来的取摸散列法好很多。

适用范围

快速查找，删除的基本数据结构，通常需要总数据量可以放入内存。

基本原理及要点

hash 函数选择，针对字符串，整数，排列，具体相应的 hash 方法。

碰撞处理，一种是 open hashing，也称为拉链法；另一种就是 closed hashing，也称开地址法，opened addressing。

散列冲突的解决方案：

1. 建立一个缓冲区，把凡是拼音重复的人放到缓冲区中。当我通过名字查找人时，发现找的不对，就在缓冲区里找。

2. 进行再探测。就是在其他地方查找。探测的方法也可以有很多种。

（1）在找到查找位置的 index 的 index-1，index+ 1 位置查找，index-2，index+ 2 查找，依次类推。这种方法称为线性再探测。

（2）在查找位置 index 周围随机的查找。称为随机在探测。

（3）再哈希。就是当冲突时，采用另外一种映射方式来查找。

这个程序中是通过取模来模拟查找到重复元素的过程。对待重复元素的方法就是再哈希：对当前 key 的位置 +7。最后，可以通过全局变量来判断需要查找多少次。我这里通过依次查找 26 个英文字母的小写计算的出了总的查找次数。显然，当总的查找次数 / 查找的总元素数越接近 1 时，哈希表更接近于一一映射的函数，查找的效率更高。

扩展

d-left hashing 中的 d 是多个的意思，我们先简化这个问题，看一看 2 -left hashing。2-left hashing 指的是将一个哈希表分成长度相等的两半，分别叫做 T1 和 T2，给 T1 和 T2 分别配备一个哈希函数，h1 和 h2。在存储一个新的 key 时，同 时用两个哈希函数进行计算，得出两个地址 h1[key]和 h2[key]。这时需要检查 T1 中的 h1[key]位置和 T2 中的 h2[key]位置，哪一个 位置已经存储的（有碰撞的）key 比较多，然后将新 key 存储在负载少的位置。如果两边一样多，比如两个位置都为空或者都存储了一个 key，就把新 key 存储在左边的 T1 子表中，2-left 也由此而来。在查找一个 key 时，必须进行两次 hash，同时查找两个位置。

问题实例（海量数据处理）

我们知道 hash 表在海量数据处理中有着广泛的应用，下面，请看另一道百度面试题：

题目：海量日志数据，提取出某日访问百度次数最多的那个 IP。
方案：IP 的数目还是有限的，最多 2^32 个，所以可以考虑使用 hash 将 ip 直接存入内存，然后进行统计。

实现

https://www.cnblogs.com/liute…

散列表解决冲突的方式有多种，这里采用了分离链接法，除此外还有开放地址法和双散列。

Vocabulary 类是用来储存单词的类，用于实现一个离线词典的数据方案，当然这并不是最高效的方法，但是我认为是比较容易理解的方法，对于初学哈希表的人来说还是比较容易接受的。

Code

/************************************************************************/
/* 文件说明：/* 采用分离链接法实现哈希表，采用 C ++ 标准库中的 vector 和 list 实现
/*
/************************************************************************/
#include <vector>
#include <list>
#include <string>

class Vocabulary;

int hash(const std::string & key, const int &tableSize);
int hash(const int & key, const int &tableSize);
//int hash(const Vocabulary & e, const int &tableSize);

namespace stl
{

    template <typename HashedObj>
    class HashTable
    {
    public:
        //typedef vector<std::list<HashedObj> >::size_type SIZE;

        HashTable(int size = 101);     // 初始化哈希表的大小
        ~HashTable(){}
        bool contains(const HashedObj & obj);
        bool insert(const HashedObj & obj);
        bool remove(const HashedObj & obj);
    private:

        std::vector<std::list<HashedObj> > theList;   // 哈希表
        int myhash(const HashedObj & obj) const;   // 哈希函数
    };


    // 函数定义
    template <typename HashedObj>
    HashTable<HashedObj>::HashTable(int size /*= 101*/)
    {
        /* 根据哈希表的大小分配 vector 的空间 */
        theList.reserve(size);
        theList.resize(size);
    }

    template <typename HashedObj>
    int HashTable<HashedObj>::myhash(const HashedObj & obj) const
    {
        // 根据 object 不同调用不同版本的 hash 重载函数
        return hash(obj, theList.size());
    }

/************************************************************************/
/* 函数名称：contains
/* 函数功能：查找指定对象是否在哈希表中
/* 返回值：存在返回 true，不存在返回 false
/************************************************************************/
    template <typename HashedObj>
    bool HashTable<HashedObj>::contains(const HashedObj & obj)
    {int iHashValue = myhash(obj);
        const std::list<HashedObj> & tempList = theList[iHashValue];

        std::list<HashedObj>::const_iterator it = tempList.cbegin();

        for (; it != tempList.cend() && *it != obj; ++it);

        if(it != tempList.cend())
            return true;
        else
            return false;
    }

/************************************************************************/
/* 函数名称：insert
/* 函数功能：向 hash 表中插入元素，如果元素已经存在则返回 false，不存在则在链表的最前面插入
/* 返回值：成功返回 true，失败返回返回 false
/************************************************************************/
    template <typename HashedObj>
    bool HashTable<HashedObj>::insert(const HashedObj & obj)
    {int iHashValue = myhash(obj);

        std::list<HashedObj> & tempList = theList[iHashValue];
        if (contains(obj))
        {return false;   // 已经存在返回 false}

        tempList.push_back(obj);
        return true;
    }

    /************************************************************************/
    /* 函数名称：remove
    /* 函数功能：从哈希表中删除指定元素，如果元素不存在则返回 false
    /* 返回值：成功返回 true，失败返回返回 false
    /************************************************************************/
    template <typename HashedObj>
    bool HashTable<HashedObj>::remove(const HashedObj & obj)
    {list<HashedObj> & tempList = theList[myhash(obj)];
        auto it = find(tempList.begin(), tempList.end(), obj);
        if (it == tempList.end())
        {return false;}
        tempList.erase(it);
        return true;
    }
}


//hash 表中存入单词表类，一个对象表示对应一个单词
class Vocabulary
{
public:
    Vocabulary(){}

    ~Vocabulary(){}

    void SetWordName(std::string name)
    {m_sWord = name;}

    void SetWordExplain(std::string explain)
    {m_sExplain = explain;}

    const std::string getName() const
    {return m_sWord;}

    Vocabulary(const Vocabulary &vc){ }

    Vocabulary& operator= (const Vocabulary & v)
    {
        m_sWord = v.m_sWord;
        m_sExplain = v.m_sExplain;
        return *this;
    }




private:
    std::string m_sWord;
    std::string m_sExplain;
};

bool operator== (const Vocabulary & word1, const Vocabulary & word2)
{if (word1.getName() == word2.getName())
    {return true;}
    else
    {return false;}
}

bool operator!= (const Vocabulary & word1, const Vocabulary & word2)
{return !(word1 == word2);
}

int hash(const Vocabulary & e,const int &tableSize)
{return hash(e.getName(), tableSize);
}

int hash(const std::string & key, const int &tableSize)
{// 采用公式：h = (k1*32 + k2) * 32 + k3，将其扩展到 n 次多项式
    long long int hashVal = 0;
    int count = 0;
    for (auto it = key.begin(); it != key.end(); ++it)
    {if (count++ % 2 == 0)
        {hashVal += (hashVal << 5) + *it;
        }

    }
    return hashVal %= tableSize;
}

int hash(const int & key, const int &tableSize)
{return key % tableSize;}

Hash 函数的构造

https://blog.csdn.net/qq_4080…

直接定址法

此类函数取关键码的某个线性函数值作为散列地址：hash (key) = a * key + b {a, b 为常数}

这类散列函数是一对一的映射，一般不会产生冲突。但是，它要求散列地址空间的大小与关键码集合的大小相同。

数字分析法

构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址。
适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。

例：有 80 个记录，关键字为 8 位十进制数，哈希地址为 2 位十进制数

平方取中法

取关键字平方后中间几位作哈希地址。适于关键字位数不定情况。

具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间

几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀

折叠法

此方法把关键码自左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。

把这些部分的数据叠加起来，就可以得到具有该关键码的记录的散列地址。有两种叠加方法：

移位法 — 把各部分的最后一位对齐相加；

分界法 — 各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址。

一般当关键码的位数很多，而且关键码每一位上数字的分布大致比较均匀时，可用这种方法得到散列地址。

除数留余法

设散列表中允许的地址数为 m, 散列函数为：

hash (key) = key % p p <= m

若 p 取 100，则关键字 159、259、359 互为同义词。我们选取的 p 值应尽可能使散列函数计算得到的散列地址与各位相关，根据经

验，p 最好取一个不大于 m，但最接近于或等于 m 的质数 p, 或选取一 个不小于 20 的质因数的合数作为除数（比如 8 = 222，2 是

8 的质因数，8 是合数）

示例：有一个关键码 key = 962148，散列表大小 m = 25，即 HT[25]。取质数 p= 23。散列函数 hash (key) = key % p。则散列地址

为 hash (962148) = 962148 % 23 = 12

可以按计算出的地址存放记录。需要注意的是，使用上面的散列函数计算出来的地址范围是 0 到 22，因此，从 23 到 24 这几个散列地

址实际上在一开始是不可能用散列函数计算出来的，只可能在处理溢出时达到这些地址。

乘余取整法

使用此方法时，先让关键码 key 乘上一个常数 A (0 < A < 1)，提取乘积的小数部分。然后，再用整数 n 乘以这个值，对结果向下取

整，把它做为散列的地址。

随机数法

选择一个随机函数，取关键字的随机函数值为它的散列地址，即 hash(key) = random(key)；其中 random 为伪随机函数，但要保证函

数值是在 0 到 m - 1 之间

处理冲突

开放定址法（再散列）

基本思想：当关键字 key 的哈希地址 p =H（key）出现冲突时，以 p 为基础，产生另一个哈希地址 p1，如果 p1 仍然冲突，再以 p 为基础，产生另一个哈希地址 p2，…，直到找出一个不冲突的哈希地址 pi，将相应元素存入其中。这种方法有一个通用的再散列函数形式：

        Hi=（H（key）+di）% m   i=1，2，…，n

其中 H（key）为哈希函数，m 为表长，di 称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。

线性探测再散列

dii=1，2，3，…，m-1 冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

二次探测再散列

di=12，-12，22，-22，…，k2，-k2 (k<=m/2) 冲突发生时，在表的左右进行跳跃式探测，比较灵活。

伪随机探测再散列

di= 伪随机数序列。具体实现时，应建立一个伪随机数发生器，（如 i =(i+p) % m），并给定一个随机数做起点。

再哈希

这种方法是同时构造多个不同的哈希函数：Hi=RH1（key）i=1，2，…，k

当哈希地址 Hi=RH1（key）发生冲突时，再计算 Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

拉链法

基本思想: 将所有哈希地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

例如: 已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表长度为 13，哈希函数为：H（key）= key % 13，则用链地址法处理冲突的结果如图所示：

位置 Entry

    0
    1  -->  40 --> 27 --> 53
    2
    3  -->  16 --> 42
    4
    5
    6  -->  32 --> 71

    7
    8
    9
    10 -->  36 --> 49
    11 -->  24
    12 -->  64

建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表

二维数组

矩阵

code

此程序仅提供一个思路。

//Matrix.h
#ifndef _MATRIX_CLL_H__
#define _MATRIX_CLL_H__
#include "pch.h"


class Matrix{
private:
    int row, col;
    double ** data;
    void Initialize();//* 初始化矩阵
public:
    Matrix(int n);//* 初始化全 0 方阵
    Matrix(int r, int c);//* 初始化 r 行 c 列的全 0 矩阵
    Matrix(int r, int c, double val);//* 初始化 r 行 c 列的全 val 矩阵
    ~Matrix();
    
    Matrix& operator=(const Matrix&);//* 矩阵的复制
    Matrix& operator=(double *);//* 将数组的值传给矩阵
    Matrix& operator+=(const Matrix&);//* 矩阵加法
    Matrix& operator-=(const Matrix&);//* 矩阵减法
    Matrix& operator*=(const Matrix&);
    Matrix operator*(const Matrix & m) const;
    void Show()const;//* 矩阵显示
    static Matrix SwapMatris(const Matrix & m);//* 矩阵转置
    Matrix Inverse(Matrix);//* 矩阵求逆
    void SwapRow(int, int);//* 初等行变换

    double Point(int i, int j)const{return this->data[i][j]; }//* 返回第 i 行，第 j 列的数字
    int GetRow()const{ return this->row;}
    int GetCol()const{ return this->col;}
    double Det();//* 计算矩阵对应的行列式
    static Matrix Eye(int);//* 创造一个单位矩阵
    static Matrix Solve(const Matrix&, const Matrix&); //* 求解线性方程组 Ax=b
    Matrix GaussianEliminate();//* 高斯消元法
    friend std::istream& operator>>(std::istream&, Matrix&);//* 实现矩阵输入
};

#endif

/*
pch.h 中仅仅放入了需要使用到的头文件
*/
//Matrix.cpp
#include "Matrix.h"
#include "pch.h"

using std::endl;
using std::cout;
using std::istream;

const double EPS = 1e-10;

void Matrix::Initialize(){data = new double*[this->row];
    for(int i = 0; i < this->row; ++i){data[i] = new double[this->col];
    }
}
Matrix::Matrix(int n){
    this->row = this->col = n;
    Initialize();
    for(int i = 0; i < this->row; i++){for(int j = 0; j < this->col; j++){data[i][j] = 0;
        }
    }
}
Matrix::Matrix(int r, int c){
    this->row = r;
    this->col = c;
    Initialize();
    for(int i = 0; i < this->row; i++){for(int j = 0; j < this->col; j++){data[i][j] = 0;
        }
    }
}
Matrix::Matrix(int r, int c, double val){
    this->row = r;
    this->col = c;
    Initialize();
    for(int i = 0; i < this->row; i++){for(int j = 0; j < this->col; j++){data[i][j] = val;
        }
    }
}
Matrix::~Matrix(){for(int i = 0; i < this->row; ++i){delete [] data[i];
    }
    delete [] data;}
Matrix& Matrix::operator=(const Matrix& m){if(this == &m){return *this;}
    if(this->row != m.row || this->col != m.col){for(int i = 0; i < this->row; ++i){delete [] data[i];
        }
        delete [] data;
        this->row = m.row;
        this->col = m.col;
        Initialize();}
    for(int i = 0; i < this->row; i++){for(int j = 0; j < this->col; j++){data[i][j] = m.data[i][j];
        }
    }
    return *this;
}
//* 将数组的值传递给矩阵（要求矩阵的大小已经被声明过）Matrix& Matrix::operator=(double *a){for(int i = 0; i < this->row; i++){for(int j = 0; j < this->col; j++){data[i][j] = *(a+i*col+j);
        }
    }
    return *this;
}
//* += 操作
Matrix& Matrix::operator+=(const Matrix& m){for(int i = 0; i < this->row; i++){for(int j = 0; j <this->col; j++){data[i][j] += m.data[i][j];
        }
    }
}
//* -=
Matrix& Matrix::operator-=(const Matrix& m){for(int i = 0; i < this->row; i++){for(int j = 0; j <this->col; j++){data[i][j] -= m.data[i][j];
        }
    }
}
//* *=
Matrix& Matrix::operator*=(const Matrix& m){Matrix temp(row,col);//* 若 C =AB, 则矩阵 C 的行数等于 A 的列数，C 的列数等于 B 的列数
    for(int i = 0; i < temp.row; i++){for(int j = 0; j < temp.col; j++){for(int k = 0; k < this->col; k++){temp.data[i][j] += (data[i][j] * m.data[i][j]);
            }
        }
    }
    *this = temp;
    return *this;
}
//* 实现矩阵乘法
Matrix Matrix::operator*(const Matrix& m) const {Matrix ba_M(row,col,0.0);
    for(int i = 0; i < row; i++){for(int j = 0; j < m.col; j++){for(int k = 0; k < col; k++){ba_M.data[i][j] += (data[i][j] * m.data[i][j]);
            }
        }
    }
    return ba_M;
}

//* 解方程组 Ax=b
Matrix Matrix::Solve(const Matrix& A,const Matrix &b){
    //* 高斯消元实现 Ax= b 的方程求解
    for(int i=0; i < A.row; i++){if(A.data[i][i] == 0){cout<<"请重新输入"<<endl;}
        for(int j = i + 1; j < A.row; j++){for(int k = i + 1; k < A.col; k++){A.data[j][k] -= A.data[i][k] * (A.data[j][i] / A.data[i][i]);
                if(abs(A.data[j][k]) < EPS)     A.data[j][k] = 0;
            }
            b.data[j][0] -= b.data[i][0] * (A.data[j][i] / A.data[i][i]);
            if(abs(A.data[j][0]) < EPS)     A.data[j][0] = 0;
            A.data[j][i] = 0;
        }
    }

    //* 反向代换
    Matrix x(b.row,1);
    x.data[x.row-1][0] = b.data[x.row-1][0] / A.data[x.row-1][x.row-1];
    if(abs(x.data[x.row-1][0]) < EPS)   x.data[x.row-1][0] = 0;
    for(int i = x.row-2; i >= 0; i--){
        double sum = 0;
        for(int j = i + 1; j < x.row; j++){sum += A.data[i][j] * x.data[j][0];
        }
        x.data[i][0] = (b.data[i][0] - sum) / A.data[i][i];
        if(abs(x.data[i][0]) < EPS)     x.data[i][0] = 0;
    }
    return x;
}
//* 矩阵显示
void Matrix::Show()const{for(int i = 0; i < this->row; i++){for(int j = 0; j < this->col; j++){cout<<data[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}
//* 矩阵的行变换
void Matrix::SwapRow(int a, int b){
    a--;b--;
    double *temp = data[a];
    data[a] = data[b];
    data[b] = temp;
}
//* 计算矩阵行列式的值
double Matrix::Det(){
    //* 为计算行列式做一个备份
    double ** back_up;
    back_up = new double*[row];
    for(int i = 0; i < row; i++){back_up[i] = new double[col];
    }
    for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){back_up[i][j] = data[i][j];
        }
    }
    if(row != col){std::abort();//* 不是方阵就中断程序
    }
    double ans = 1;
    for(int i = 0; i < row; i++){
        //* 通过行变换的形式，使得矩阵对角线上的主元素不为 0
        if(abs(data[i][i]) <= EPS){
            bool flag = false;
            for(int j = 0; (j < col) && (!flag); j++){
                //* 若矩阵的一个对角线上的元素接近 0 且能够通过行变换使得矩阵对角线上的元素不为 0
                if((abs(data[i][j]) > EPS) && (abs(data[j][i]) > EPS)){flag = true;//* 进行互换后，data[i][j]变为 data[j][i],p[j][i]变为 p[i][i]
                    //* 对矩阵进行行变换
                    double temp;
                    for(int k = 0; k < col; k++){temp = data[i][k];
                        data[i][k] = data[j][k];
                        data[j][k] = temp;
                    }
                }
            }
            if(flag)    return 0;
        }
    }
    for(int i = 0; i < row; i++){for(int j = i + 1; j < row; j++){for(int k = i + 1; k < col; k++){data[j][k] -= data[i][k] * (data[j][i] * data[i][i]);
            }
        }
    }
    for(int i = 0; i < row; i++){ans *= data[i][i];
    }
    for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){data[i][j] = back_up[i][j];
        }
    }
    return ans;
}

//* 矩阵求逆
Matrix Matrix::Inverse(Matrix A){if(A.row != A.col){
        std::cout << "只能求方阵的逆矩阵！"<<std::endl;
        std::abort();}
    double temp;
    Matrix A_B = Matrix(A.row, A.col);
    A_B = A;// 给 A 做备份
    Matrix B = Eye(A.row);
    // 将小于 EPS 的数字全部置 0
    for(int i = 0; i < A.row; i++){for(int j = 0; j < A.col; j++){if(abs(A.data[i][j]) <= EPS){A.data[i][j] = 0; 
            }                 
        }
    }
    // 选择需要交换的两行选主元
    for(int i = 0; i < A.row; i++){if(abs(A.data[i][i]) <= EPS){
            bool flag = false;
            for(int j = 0; (j < A.row) && (!flag); j++){if((abs(A.data[i][j]) > EPS) && (abs(A.data[j][i]) > EPS)){
                    flag = true;
                    for(int k = 0; k < A.col; k++){temp = A.data[i][k];
                        A.data[i][k] = A.data[j][k];
                        A.data[j][k] = temp;
                        temp = B.data[i][k];
                        B.data[i][k] = B.data[j][k];
                        B.data[j][k] = temp;
                    }
                }
            }
            if(!flag){
                std::cout <<"逆矩阵不存在"<<std::endl;
                std::abort();}
        }
    }
    //* 通过初等变换变成上三角矩阵
    double temp_rate;
    for(int i = 0; i < A.row; i++){for(int j = i + 1; j < A.row; j++){temp_rate = A.data[j][i] / A.data[i][i];
            for(int k = 0; k < A.col; k++){A.data[j][k] -= A.data[i][k] * temp_rate;
                B.data[j][k] -= B.data[i][k] * temp_rate;
            }
            A.data[j][i] = 0;
        }
    }
    //* 使得对角线元素均为 1
    for(int i = 0; i < A.row; i++){temp = A.data[i][i];
        for(int j = 0; j < A.col; j++){A.data[i][j] /= temp;
            B.data[i][j] /= temp;
        }
    }
    //std::cout<<"算法检测，若可靠输出上三角矩阵"<<std::endl;
    //* 将一变为上三角矩阵的 A 变为单位矩阵
    for(int i = A.row - 1; i >= 1; i--){for(int j = i - 1; j >= 0; j--){temp = A.data[i][j];
            for(int k = 0; k < A.col; k++){A.data[j][k] -= A.data[i][k] * temp;
                B.data[j][k] -= B.data[i][k] * temp;
            }
        }
    }
    std::cout<<"算法检测，若可靠输出上三角矩阵"<<std::endl;
    for(int i = 0; i < A.row; i++){for(int j = 0; j < A.col; j++){printf("%7.4lf\t\t",A.data[i][j]);
        }
        cout<<endl;
    }
    A = A_B;// 还原 A
    return B;// 返回逆矩阵
}
//* 生成一个单位矩阵
Matrix Matrix::Eye(int n){Matrix A(n);
    for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){if(i == j){A.data[i][j] = 1;
            }
            else{A.data[i][j] = 0;
            }
        }
    }
    return A;
}
//* 实现矩阵的转置
Matrix Matrix::SwapMatris(const Matrix & m){int col_size = m.GetCol();
    int row_size = m.GetRow();
    Matrix mt(col_size, row_size);
    for(int i = 0; i < row_size; i++){for(int j = 0; j < col_size; j++){mt.data[i][j] = m.data[j][i];
        }
    }
    return mt;
}
//* 高斯消元法
Matrix Matrix::GaussianEliminate(){Matrix Ab(*this);
    int row_num = Ab.row;
    int col_num = Ab.col;
    int Acol = col_num - 1;
    
    int i = 0, j = 0;// i，j 用于跟踪行和列
    while(i < row_num){
        bool flag = false;
        while(j < Acol && !flag){if(Ab.data[i][j] != 0){flag = true;}
            else{
                int max_row = i;
                double max_val = 0;
                for(int k = i + 1; k < row; ++k){double cur_abs = Ab.data[k][j] >= 0 ? Ab.data[k][j] : -1 * Ab.data[k][j];
                    if(cur_abs > max_val){
                        max_row = k;
                        max_val = cur_abs;
                    }
                }
                if(max_row != i){Ab.SwapRow(max_row, i);
                    flag = true;
                }
                else{j++;}
            }
        }
        if(flag){for(int t = i + 1; t < row; t++){for(int s = j + 1; s < col; s++){Ab.data[t][s] = Ab.data[t][s] * (Ab.data[t][j] / Ab.data[i][j]);
                    if(abs(Ab.data[t][s]) < EPS){Ab.data[t][s] = 0;
                    }
                }
                Ab.data[t][j] = 0;
            }
        }
        i++;j++;
    }
    return Ab;
}
//* 实现矩阵的输入 
istream& operator>>(istream& is, Matrix& m){for(int i = 0; i < m.row; i++){for(int j = 0; j < m.col; j++){is >> m.data[i][j];
        }
    }
    return is;
}

矩阵加速

https://blog.csdn.net/weixin_…

例 1 斐波那契数列

题目链接：https://www.luogu.com.cn/prob…

题目大意

求第 n 项斐波那契数列摸 1000000007 的值，n 在 long long 范围内

输入

一行，n

输出

f(n)%1000000007 的值

样例输入

10
1
样例输出

55
1
分析

首先，直接递推肯定超时，可以观察如下两个式子

$$
f[n]=f[n-1]\times 1+f[n-2]\times 1
$$

$$
f[n-1]=f[n-1]\times 1+f[n-2]\times 0
$$

令

$$
令 A =\begin{bmatrix}
1 & 1\\1
&0
\end{bmatrix}
$$

​

$$
则 A^{n} \times \begin{bmatrix}
f(n-1)\\f(n-2)

\end{bmatrix}=\begin{bmatrix}
f(n) \\f(n-1)

\end{bmatrix}
$$

其中 A^n 可以通过矩阵快速幂得到，这样就可以通过矩阵 A 来加速递推运算

Code

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll mod = 1000000007;

inline mat mult (mat A, mat B) {int row = A.size(), col = B[0].size(), l = B.size();
    mat C(row, vec(col));
    for(int i = 0; i < row; i++)
        for(int j = 0; j < col; j++)
            for(int k = 0; k < l; k++)
                C[i][j] = C[i][j] % mod + A[i][k] * B[k][j] % mod;
    return C;
}

mat Power(mat &A, ll m) { // 求快速幂
    ll n = A.size();
    mat res(n, vec(n));
    for(int i = 0; i < n; i++)
        res[i][i] = 1;
    while(m) {if(m & 1) res = mult(res, A);
        m >>= 1;
        A = mult(A, A);
    }
    return res;
}

int main () {
    ll n;
    mat a(2, vec(2));
    cin >> n;
    a[0][0] = 1, a[0][1] = 1; \\ 通过矩阵 a 来进行加速
    a[1][0] = 1, a[1][1] = 0;
    mat t = Power(a, n);
    cout << t[1][0] % mod << "\n";
    return 0;
}

例 2 数列

题目链接：https://www.luogu.com.cn/prob…

题目大意：a[1] = a[2] = a[3] = 1,a[x] = a[x-3]+a[x-1] (x>3) 求 a 数列的第 n 项对 1000000007 取余的值。

输入：第一行一个整数 T，表示询问个数。以下 T 行，每行一个正整数 n。

输出：每行输出一个非负整数表示答案

输入 Case：

​ 3

​ 6

​ 8

​ 10

输出 Case：

​ 4

​ 9

​ 19

分析：同样使用矩阵加速递推，关键在于找到哪个矩阵来进行加速，由于这个递推公式跨度有 3 哥长度，所以可以写 3 个递推式：

$$
f[n] = 1 \times f[n-1] + 0 \times f[n-2] + 1 \times f[n-3]
$$

$$
f[n-1] = 1 \times f[n-1] + 0 \times f[n-2] + 0 \times f[n-3]
$$

$$
f[n-2] = 0 \times f[n-1] + 1 \times f[n-2] + 0 \times f[n-3]
$$

同样提取系数，转换为矩阵乘法

$$
\begin{bmatrix}
1 & 0 & 1\\
1 & 0 & 0\\
0 & 1 & 0
\end{bmatrix} \times \begin{bmatrix}
f(n-1) \\f(n-2)
\\f(n-3)

\end{bmatrix} = \begin{bmatrix}
f(n)\\f(n-1)
\\f(n-2)

\end{bmatrix}
$$

$$
令 A =\begin{bmatrix}
1 & 0 & 1 \\
1 & 0 & 0\\
0 & 1 & 0
\end{bmatrix}
$$

$$
\therefore A^{-3} \times \begin{bmatrix}
f(3)\\f(2)
\\f(1)

\end{bmatrix}=\begin{bmatrix}
f(n) \\ f(n-1)
\\ f(n-2)

\end{bmatrix}
$$

$$
\therefore \begin{bmatrix}
f(3)\\f(2)
\\f(1)

\end{bmatrix} = \begin{bmatrix}
1 \\1
\\1

\end{bmatrix}
$$

#include <iostream>
#include <cctype>
#include <vector>
#include <cstdio>
#define ll long long
#define in(a) a = read();
using namespace std;
inline int read () {int f = 1, x = 0; char c = getchar();
    while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
    while(isdigit(c)) {x = (x << 3) + (x << 1) + c - 48; c = getchar();}
    return f*x;
}

typedef vector<ll> vec;
typedef vector<vec> mat;
const ll mod = 1e9+7;

inline mat mul(mat A, mat B) {int row = A.size(), col = B[0].size(), l = B.size();
    mat C(row, vec(col));
    for(int i = 0; i < row; i++)
        for(int j = 0; j < col; j++)
            for(int k = 0; k < l; k++)
                C[i][j] = C[i][j] % mod + A[i][k] * B[k][j] % mod;
    return C;
}

inline mat powMod (mat A, int m) {int n = A.size();
    mat res(n, vec(n));
    for(int i = 0; i < n; i++)
        res[i][i] = 1;
    while(m) {if(m & 1) res = mul(res, A);
        m >>= 1;
        A = mul(A, A);
    }
    return res;
}

int main () {
    int T1, n;
    mat F(3, vec(3)), e(3, vec(1)); \\F 矩阵用来加速，e 表示初始的 f(3)，f(2)，f(1)
    F[0][0] = 1, F[0][1] = 0, F[0][2] = 1;
    F[1][0] = 1, F[1][1] = 0, F[1][2] = 0;
    F[2][0] = 0, F[2][1] = 1, F[2][2] = 0;
    e[0][0] = 1, e[1][0] = 1, e[2][0] = 1;
    in(T1);
    while (T1 --) {in(n);
        n -= 3;
        if(n <= 0) printf("1\n");
        else {mat t = powMod(F, n);
            t = mul(t, e);
            printf("%lld\n", t[0][0] % mod); 
        } 
    }
    return 0;
}

例 3 Blocks

题目链接：http://poj.org/problem?id=3734

题目大意： N 个方块排成一列，有红、黄、绿、蓝四种颜色，对方块染色，求当红色方块数和绿色方块数同为偶数个数的时候有多少种染色方案。结果对 10007 取余数。

输入：第一行一个 T，表示测试数据数量（1 <= T <= 100）; 接下来 T 行，每行一个 n，表示方块的数量。（1 <= N <=10^9）

输出：对于每一个 n，输出一个结果，每一个结果换一行

输入 Case：

​ 2

​ 1

​ 2

输出 Case：

​ 2

​ 6

分析：首先要找出递推关系式，然后才能用矩阵加速。

• 红绿都是偶数的方案数为 Ai
• 红绿其中有一个偶数另一个是奇数的方案数为 Bi
• 红绿都是奇数的方案数为 Ci

$$
考虑 A_{i+1} = 2 \times A_{i} + B_{i}
$$

(递推 A 的第 i+ 1 块的时候，为保证红绿都为偶数。上一种红绿都是偶数的时候，新来一块可以选择黄蓝染色，同时还有上一种红绿只有一个为奇数，那么新来的一块只能染成这个奇数的颜色)

$$
考虑 B_{i},B_{i+1} = 2 \times A_{i} + 2 \times B_{i} + 2 \times C_{i}
$$

（递推 B 的第 i+ 1 块的时候，为了保证红绿只有一奇。上一种红绿都为偶数，新来一块可以选择红或者绿，上一种红绿有一个为奇数，新来的一块可以染黄或者蓝色，如果上一种红绿都为奇数，新来的一块染红或者绿）

$$
考虑 C_{i}, C_{i+1} = B_{i} + 2 \times C_{i}
$$

所以：

$$
A_{i+1}=2\times A_{i}+1\times B_{0}+0\times C_{i}
$$

$$
B_{i+1}=2\times A_{i}+2\times B_{0}+2\times C_{i}
$$

$$
C_{i+1}=0\times A_{i}+1\times B_{0}+2\times C_{i}
$$

提取系数，转换矩阵乘法：

$$
\begin{bmatrix}
2 & 1 & 0\\
2 & 2 & 2\\
0 & 1 & 2
\end{bmatrix}\times \begin{bmatrix}
A(n-1) \\ B(n-1) \\ C(n-1)
\end{bmatrix}=\begin{bmatrix}
A(n) \\ B(n) \\ C(n)
\end{bmatrix}
$$

$$
令 A =\begin{bmatrix}
2 & 1 & 0\\
2 & 2 & 2\\
0 & 1 & 2
\end{bmatrix}
$$

$$
则 A_{n} =\begin{bmatrix}
A(0)\\B(0)\\C(0)
\end{bmatrix}
$$

$$
\begin{bmatrix}
A(0)\\B(0)\\C(0)
\end{bmatrix}=\begin{bmatrix}
1\\0
\\0

\end{bmatrix}
$$

Code

#include <iostream>
#include <cctype>
#include <vector>
#include <cstdio>
#define ll long long
#define in(a) a = read();
using namespace std;
inline int read () {int f = 1, x = 0; char c = getchar();
    while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();}
    while(isdigit(c)) {x = (x << 3) + (x << 1) + c - 48; c = getchar();}
    return f*x;
}

typedef vector<ll> vec;
typedef vector<vec> mat;
const ll mod = 10007;

inline mat mul(mat A, mat B) {int row = A.size(), col = B[0].size(), l = B.size();
    mat C(row, vec(col));
    for(int i = 0; i < row; i++)
        for(int j = 0; j < col; j++)
            for(int k = 0; k < l; k++)
                C[i][j] = C[i][j] % mod + A[i][k] * B[k][j] % mod;
    return C;
}

inline mat powMod (mat A, int m) {int n = A.size();
    mat res(n, vec(n));
    for(int i = 0; i < n; i++)
        res[i][i] = 1;
    while(m) {if(m & 1) res = mul(res, A);
        m >>= 1;
        A = mul(A, A);
    }
    return res;
}

int main () {
    int T1, n;
    mat F(3, vec(3)), e(3, vec(1));
    F[0][0] = 2, F[0][1] = 1, F[0][2] = 0;
    F[1][0] = 2, F[1][1] = 2, F[1][2] = 2;
    F[2][0] = 0, F[2][1] = 1, F[2][2] = 2;
    e[0][0] = 1, e[1][0] = 0, e[2][0] = 0;
    in(T1);
    while (T1 --) {in(n);
        mat t = powMod(F, n);
        t = mul(t, e);
        printf("%lld\n", t[0][0] % mod); 
    }
    return 0;
}