难度：中等
给你一个长度为 偶数 n 的整数数组 nums 和一个整数 limit 。每一次操作，你可以将 nums 中的任何整数替换为 1 到 limit 之间的另一个整数。

如果对于所有下标 i（下标从 0 开始），nums[i] + nums[n - 1 - i] 都等于同一个数，则数组 nums 是 互补的 。例如，数组 [1,2,3,4] 是互补的，因为对于所有下标 i ，nums[i] + nums[n - 1 - i] = 5 。

返回使数组 互补 的 最少 操作次数。

示例 1：

输入：nums = [1,2,4,3], limit = 4
输出：1
解释：经过 1 次操作，你可以将数组 nums 变成 [1,2,2,3]（加粗元素是变更的数字）：
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
对于每个 i ，nums[i] + nums[n-1-i] = 4 ，所以 nums 是互补的。

示例 2：

输入：nums = [1,2,2,1], limit = 2
输出：2
解释：经过 2 次操作，你可以将数组 nums 变成 [2,2,2,2] 。你不能将任何数字变更为 3 ，因为 3 > limit 。

示例 3：

输入：nums = [1,2,1,2], limit = 2
输出：0
解释：nums 已经是互补的。

提示：

n == nums.length
2 <= n <= 105
1 <= nums[i] <= limit <= 105
n 是偶数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-moves-to-make-array-complementary

解法一：树状数组（区间更新，单点更新）

// 区间更新，单点求值
// 单点的值用前缀和表示 即 c[i] = a[1] + a[2] + ... + a[i - 1] + a[i]
// 区间[x, y]增加k 即a[x] + k, a[y + 1] - k,这样对于x->y的前缀和都加k，y+1前缀和并没变
class BIT{
public:
    int n, m;
    vector<int> c;

    BIT(int _n) : n(_n),  c(_n + 1){
    }
    
    int lowbit(int x){
        return x & (-x);
    }
    //更新单点信息
    void _update(int i, int k){
        while(i <= n){
            c[i] += k;
            i += lowbit(i);
        }
    }
    
    int getSum(int i){
        int res = 0;
        while(i > 0){
            res += c[i];
            i -= lowbit(i);
        }
        return res;
    }
    //区间[x, y]增加k
    void update(int x, int y, int k){
        _update(x, k);
        _update(y + 1, -k);
    }
};

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        BIT bit(limit * 2);
        int size = nums.size();
        for(int i = 0; i < size / 2; i++){
            int minNum = min(nums[i], nums[size - 1 - i]);
            int maxNum = max(nums[i], nums[size - 1 - i]);
            bit.update(1, minNum, 2);
            bit.update(maxNum + limit + 1, limit * 2, 2);
            bit.update(minNum + 1, maxNum + limit, 1);
            bit.update(nums[i] + nums[size - 1 - i],nums[i] + nums[size - 1 - i], -1);
        }
        int minCount = size;
        int minSum = 0;
        int a = *min_element(nums.begin(), nums.end());
        int b = *max_element(nums.begin(), nums.end());
        for(int i = a; i <= b + limit; i++){
            if(bit.getSum(i) < minCount){
                minCount = bit.getSum(i);
                minSum = i;
            }
        }
        int ans = 0;
        for(int i = 0; i < size / 2; i++){
            if(nums[i] + nums[size - 1 - i] == minSum)
                continue;
            int minNum = min(nums[i], nums[size - 1 - i]);
            int maxNum = max(nums[i], nums[size - 1 - i]);
            if(minNum + 1 > minSum || maxNum + limit < minSum)
                ans += 2;
            else
                ans += 1;
        }
        return ans;
    }
};

解法二：差分数组

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        vector<int> count(limit * 2 + 2, 0);
        int size = nums.size();
        for(int i = 0; i < size / 2; i++){
            int a = max(nums[i], nums[size - 1 - i]);
            int b = min(nums[i], nums[size - 1 - i]);
            int sum = nums[i] + nums[size - 1 - i];
            // [0, b] and [a + limit + 1, limit * 2 + 1] need 2
            // [b + 1, sum - 1] and [sum + 1, a + limit] need 1
            count[0] += 2, count[b + 1] -= 2;
            count[a + limit + 1] += 2, count[limit * 2 + 1] -= 2;
            count[b + 1] += 1, count[sum] -= 1;
            count[sum + 1] += 1, count[a + limit + 1] -= 1;
        }
        int res = INT_MAX;
        for(int i = 1; i <= limit * 2; i++){
            count[i] += count[i - 1];
            if(count[i] < res)
                res = count[i];
        }
        return res;
    }
};

两种方法底层的区间更新，单点查询的原理都是差不多的。

使数组互补的最少操作次数（树状数组/差分数组）

原文：https://www.cnblogs.com/bgyx-hyyy/p/14061837.html