C++中的sort函数和swap函数 前缀和与差分

C++中的sort函数和swap函数 前缀和与差分

一、sort函数

sort函数的头文件为： #include；

常用格式：sort(vec.begin(),vec.end()) :对向量进行升序排列；

sort(num,num+n):对数组num的0~n-1元素进行升序排序。

如果想要降序排列：sort(begin_pointer,begin_pointer+n,cmp)

其中，可以调用自己定义的cmp函数达到降序排列的目的

bool cmp(int a,int b)
{
      return a>b;
 }

二、swap函数

swap函数的头文件为： #include

因为 swap 函数的参数是两个地址，所以这样调用它：

swap(&i, &j);

作用为：交换两个数值的值

C++也可以使用引用，swap 可以这样写：

void swap(int &a, int &b)
{
    int k = a;
    a = b;
    b = k;
}

三、前缀和 

前缀和的思路是这样的，对于一个给定的数组 nums，我们额外开辟一个前缀和数组进行预处理：

int n = nums.length;
// 前缀和数组
int[] preSum = new int[n + 1];
preSum[0] = 0;
for (int i = 0; i < n; i++)
    preSum[i + 1] = preSum[i] + nums[i];

这个前缀和数组 preSum 的含义，preSum[i] 就是 nums[0..i-1] 的和。那么如果我们想求 nums[i..j] 的和，只需要一步 *** 作 preSum[j+1]-preSum[i] 即可，而不需要重新去遍历数组了。

四、差分 

如果数组A是B的前缀和，则B是A的差分。
我们构造一个数组的差分矩阵，是为了针对频繁的对数组中某个区间进行同一 *** 作。例如将序列中[l, r]之间的每个数加上c这一 *** 作，可能执行n次，每次的c不同，如果对原数组进行 *** 作，每次 *** 作都会花费O(n)的时间复杂度。如果使用该数组的差分数组进行 *** 作，每次 *** 作为O(1)。然后求差分数组的前缀和即为所求结果。

差分数组

针对[l, r]之间的每个数加上c这一 *** 作

let diffCreate = (c, l, r) => {
    diffArr[l] += c;
    diffArr[r + 1] -= c;
}

这是差分数组 *** 作的核心，对于原数组区间中每个数都要 *** 作，而差分数组就只要 *** 作两个数。因为原数组是差分数组的前缀和，所以第l个数加c，后面每个数都会加c，再把不需要的部分（r后面的数）减去c。

针对原数组快速构造差分数组

把原数组a看作全0数组b，每个位置上的数看作一次差分 *** 作。比如说如果a[1]=2，那么对全0数组b进行diffCreate(1,1,2) *** 作，相当于把从1到1区间（其实就一个数）上的每个数加2。所有的数 *** 作后得到的b就是a的差分数组。

差分矩阵也是同理。

let diffCreate = (c, x1, y1, x2, y2) => {
    diffArr[x1][y1] += c;
    diffArr[x2 + 1][y1] -= c;
    diffArr[x1][y2 + 1] -= c;
    diffArr[x2 + 1][y2 + 1] += c;
}

注意：不论是差分数组还是差分矩阵下标都要从1开始（a[1]、a[2][3]），而且前面的0位置（a[0]、a[0][0]、a[1][0]）都要置为0。因为求前缀和时（也就是求原数组）会用到，为了同一 *** 作而不对0处进行特殊判断，所以为0写起来更方便。