C语言 | Leetcode C语言题解之第327题区间和的个数

题目：

题解：

#define FATHER_NODE(i)      (0 == (i) ? -1 : ((i) - 1 >> 1))
#define LEFT_NODE(i)        (((i) << 1) + 1)
#define RIGHT_NODE(i)       (((i) << 1) + 2)
 
/* 优先队列（小根堆）。 */
typedef struct
{
    int *arr;
    int arrSize;
}
PriorityQueue;
 
/* 二进制树（01字典树）。 */
typedef struct
{
    int *arr;
    int highestBit;
}
BinaryTree;
 
/* 几个自定义函数的声明，具体实现见下。 */
static void queuePush(PriorityQueue *queue, long long *prefix, int x);
static void queuePop(PriorityQueue *queue, long long *prefix);
static int treeHighestBit(int mostVal);
static void treePush(BinaryTree *tree, int x);
static void treePop(BinaryTree *tree, int x);
static int treeSmaller(BinaryTree *tree, int x);
 
/* 主函数：
  treeSize:         二进制树的数组空间大小，等于里面最大值的3倍，具体证明略，大致就是等比数列求和的结果。
  prefix[]:         其中prefix[x]表示[0, x]范围内子数组的前缀和。这里必须以long long类型存储。
  window[]:         里面存储prefix[]数组的下标，即prefix[window[x]]才真正表示一个前缀和。
  buff1[],buff2[]:  优先队列与二进制树各自使用的数组空间。其中buff2[]必须初始化为全0。
  queue:            优先队列（小根堆），为了不打乱prefix[]数组中的数值顺序，而且window[]数组中实际存放的是下标，所以借用堆排序。
  tree:             二进制树（01字典树）。 */
int countRangeSum(int *nums, int numsSize, int lower, int upper)
{
    const int treeSize = numsSize * 3;
    int x = 0, y = 0, z = 0, t = 0, result = 0;
    long long sum = 0;
    long long prefix[numsSize];
    int window[numsSize], buff1[numsSize], buff2[treeSize];
    PriorityQueue queue;
    BinaryTree tree;
    /* 初始化。 */
    queue.arr = buff1;
    queue.arrSize = 0;
    memset(buff2, 0, sizeof(buff2));
    tree.arr = buff2;
    tree.highestBit = treeHighestBit(numsSize - 1);
    /* 计算前缀和，并将前缀和的下标放到一个小根堆里面，小根堆里面以对应的前缀和为优先级。 */
    for(x = 0; numsSize > x; x++)
    {
        sum += nums[x];
        prefix[x] = sum;
        queuePush(&queue, prefix, x);
        /* 如果[0, x]的子数组和本来就在[lower, upper]之间，计数累计。 */
        if((long long)lower <= sum && (long long)upper >= sum)
        {
            result++;
        }
    }
    /* 将前缀和数组的下标，以对应的prefix值从小到大的顺序，放到window数组中。 */
    while(0 < queue.arrSize)
    {
        window[t] = queue.arr[0];
        t++;
        queuePop(&queue, prefix);
    }
    /* 开始以滑动窗口的形式移动窗口的左右指针。 */
    for(x = 0; numsSize > x; x++)
    {
        /* 将所有prefix[window[x]] - prefix[window[y]] >= lower的下标y都加入。 */
        while(numsSize > y && prefix[window[x]] - lower >= prefix[window[y]])
        {
            treePush(&tree, window[y]);
            y++;
        }
        /* 将所有prefix[window[x]] - prefix[window[z]] > upper的下标z都移除。 */
        while(numsSize > z && prefix[window[x]] - upper > prefix[window[z]])
        {
            treePop(&tree, window[z]);
            z++;
        }
        /* 将窗口内（树内）剩余的下标值中，小于window[x]的数量加到结果中。 */
        t = treeSmaller(&tree, window[x]);
        result += t;
    }
    return result;
}
 
/* 小根堆的push操作。由于堆中存储的是prefix[]数组的下标，所以入参需带上prefix。 */
static void queuePush(PriorityQueue *queue, long long *prefix, int x)
{
    int son = queue->arrSize, father = FATHER_NODE(son);
    /* 新加入数值之后，数量加一。 */
    queue->arrSize++;
    /* 根据对应prefix[]值的大小关系，调整父子节点的位置。 */
    while(-1 != father && prefix[x] < prefix[queue->arr[father]])
    {
        queue->arr[son] = queue->arr[father];
        son = father;
        father = FATHER_NODE(son);
    }
    /* 放到实际满足父子节点大小关系的位置。 */
    queue->arr[son] = x;
    return;
}
 
/* 小根堆的pop操作。由于堆中存储的是prefix[]数组的下标，所以入参需带上prefix。 */
static void queuePop(PriorityQueue *queue, long long *prefix)
{
    int father = 0, left = LEFT_NODE(father), right = RIGHT_NODE(father), son = 0;
    /* 堆顶pop之后，数量减一。默认将堆尾的数值补充上来填补空位。 */
    queue->arrSize--;
    /* 根据对应prefix[]值的大小关系，调整父子节点的位置。 */
    while((queue->arrSize > left && prefix[queue->arr[queue->arrSize]] > prefix[queue->arr[left]])
        || (queue->arrSize > right && prefix[queue->arr[queue->arrSize]] > prefix[queue->arr[right]]))
    {
        son = (queue->arrSize > right && prefix[queue->arr[left]] > prefix[queue->arr[right]]) ? right : left;
        queue->arr[father] = queue->arr[son];
        father = son;
        left = LEFT_NODE(father);
        right = RIGHT_NODE(father);
    }
    /* 放到实际满足父子节点大小关系的位置。 */
    queue->arr[father] = queue->arr[queue->arrSize];
    return;
}
 
/* 计算二进制树中，可能出现的最大的数值，所占据的最高二进制比特。
  比如，最大值的二进制是101100(b)，那么返回的最高比特是100000(b)。特殊的，最大是0的时候返回1(b)。 */
static int treeHighestBit(int mostVal)
{
    int x = 1;
    if(0 < mostVal)
    {
        while(0 < mostVal)
        {
            x++;
            mostVal = mostVal >> 1;
        }
        x = 1 << x - 2;
    }
    return x;
}
 
/* 往二进制树中push一个数值。 */
static void treePush(BinaryTree *tree, int x)
{
    int i = 0, bit = tree->highestBit;
    /* 从最高位到最低位的顺序，该位为1就给右分支加1，为0就给左分支加1。 */
    while(0 < bit)
    {
        i = (bit & x) ? RIGHT_NODE(i) : LEFT_NODE(i);
        tree->arr[i]++;
        bit = bit >> 1;
    }
    return;
}
 
/* 从二进制树中pop一个数值。 */
static void treePop(BinaryTree *tree, int x)
{
    int i = 0, bit = tree->highestBit;
    /* 从最高位到最低位的顺序，该位为1就给右分支减1，为0就给左分支减1。 */
    while(0 < bit)
    {
        i = (bit & x) ? RIGHT_NODE(i) : LEFT_NODE(i);
        tree->arr[i]--;
        bit = bit >> 1;
    }
    return;
}
 
/* 在二进制树中查找比输入数值小的数值数量。 */
static int treeSmaller(BinaryTree *tree, int x)
{
    int i = 0, bit = tree->highestBit, result = 0;
    /* 从高位到低位的顺序查看。 */
    while(0 < bit)
    {
        /* 该位为1，则肯定比高位相同，该位为0的数值更大，即把左分支的数量加到结果中。 */
        if(bit & x)
        {
            result += tree->arr[LEFT_NODE(i)];
            i = RIGHT_NODE(i);
        }
        /* 该位为0，就往左分支走，不做任何其它处理。 */
        else
        {
            i = LEFT_NODE(i);
        }
        bit = bit >> 1;
    }
    return result;
}