小和問題和逆序對問題

小和問題，

在一個數組中，每一個數左邊的數中比當前數小的數累加起來，叫做這個數組的小和，求一個數組的小和
直接遍歷：

int littleSum1(int* arr, int L, int R)
{int temp = 0;for (int i = L; i < R + 1; i++){for (int j = L; j < i; j++){if (arr[j] < arr[i]){temp = temp + arr[j];}}}return temp;
}

使用歸并
求小和的問題可以等效為：
如求下面數組的小和

int arr[] = { 1,3,4,2,5 };

通常的思路：
1左邊沒有比1小的
3左邊比3小的：1
4左邊比4小的：1，3
2左邊比2小的：1
5左邊比5小的：1，3，4，2
加起來：1+1+3+1+1+3+4+2=16
等效為：
1右邊有4個數比1大，則會小和中有4個1，41
3右邊有2個數比3大，23
4右邊有1個數比4大，14
2右邊有1個數比2大，12
5右邊沒有數比5大，05
加起來41+23+14+12+05=16

在編寫代碼時與一般的歸并有一點不一樣，當左側數組p1和右側數組p2指向的數一樣時先拷貝右側的數，不然不知道有多少個數比左側p1指向的數大，會有漏算的情況，其中process中 if (L >= R) return 0;//此處我認為是遞歸的中止條件，很多次忘記加這個條件導致無法出結果
務必別丟

int littleSum2(int* arr, int L, int R)
{if (L >= R) return 0;return process(arr, L, R);
}
int process(int* arr, int L, int R)
{if (L >= R) return 0;//此處我認為是遞歸的中止條件，很多次忘記加這個條件導致無法出結果int mid = L + ((R - L) >> 1);return process(arr, L, mid)+ process(arr, mid + 1, R)+merge_sum(arr, L, mid, R);}
int merge_sum(int* arr, int L, int mid, int R)
{int res = 0;int i = 0;int p1 = L;int p2 = mid + 1;int* temp = new int[R - L + 1];while (p1 <= mid && p2 <= R){if (arr[p1] < arr[p2]){res = res + (R - p2 + 1) * arr[p1];temp[i++] = arr[p1++];}else{temp[i++] = arr[p2++];}}while (p1 <= mid){temp[i++] = arr[p1++];}while (p2 <= R){temp[i++] = arr[p2++];}for (int j = 0; j < R-L + 1; j++){arr[L+j] = temp[j];}delete[] temp;return res;
}

逆序對問題

在一個數組中，左邊的數如果比右邊的數大，則兩個數構成一個逆序對，請打印所有的逆序對

void Reverse_pair(int* arr, int L, int R)
{if (L >= R){cout << "無逆序對" << endl;return;}processReverse(arr, L, R);
}void processReverse(int* arr, int L, int R)
{if (L >= R)return;int mid = L + ((R - L) >> 1);processReverse(arr, L, mid);processReverse(arr, mid + 1, R);mergeReverse(arr, L, mid, R);
}
void mergeReverse(int* arr,  int L, int mid, int R)
{int i = 0;int* temp = new int[R - L + 1];int p1 = L;int p2 = mid + 1;while (p1 <= mid && p2 <= R){if (arr[p1] > arr[p2]){temp[i] = arr[p1];cout << "逆序對：" << arr[p1] << "   " << arr[p2] << endl;i = i + 1;p1 = p1 + 1;}else{temp[i++] = arr[p2++];}}while (p1 <= mid){temp[i++] = arr[p1++];}while (p2 <= R){temp[i++] = arr[p2++];}for (int j = 0; j < R - L + 1; j++){arr[L + j] = temp[j];}delete[] temp;
}