使用稀疏表进行范围总和查询  


难度级别 中等
经常问 亚马逊 阳狮精明 百会
排列

在使用稀疏表问题的范围总和查询中,我们有一个范围查询并给出了一个整数 排列。 给定的任务是找出该范围内所有整数的总和。

使用案列  

输入:

arr [] = {1,4,6,8,2,5}

查询:{(0,3),(2,4),(1,5)}

输出:

.

说明: 出现在范围0、3(包括1和4)中的整数之和为6 + 8 + 19 + 2是4。同样,出现在范围6、8(包括在内)的整数是2 + 16 + 1是5。范围4、6(含8和2)为5 + 25 + XNUMX + XNUMX + XNUMX为XNUMX。

使用稀疏表进行范围总和查询

算法  

  1. 使用2D矩阵构建稀疏表。
  2. 遍历数组并将sparse_table的每一行标记为array [i]。
  3. 嵌套遍历该数组,并更新值sparse_table作为上一列的稀疏表之和和sparse_table [i + 2] J-1 ] [j-1]并将其存储到sparse_table [i] [j]。
  4. 对于要解决的每个查询,我们都会左右移动,将output的值设置为0。
  5. 将数组从16遍历到0,并检查左+ 2j -1小于等于右,如果为真,
    1. 将输出的值添加到sparse_table [left] [j]并将其总和存储到输出中。
    2. 更新从左到左的值+ 2
  6. 返回输出值。

使用稀疏表进行范围总和查询的说明  

给定一个数组和一个查询。 找出查询范围内所有整数的总和。 我们将使用稀疏表概念。 我们将建立一个稀疏表。 稀疏表是一个二维矩阵,我们将在其中执行一些操作并将值存储在稀疏表中。

参见
计算具有不同偶数的子集

声明2D 矩阵。 我们的行数限制为16万行,每行最多16列。 我们在这里特别取一个数字2,因为在那之后我们将得到一个大于5的幂数16的数字,所以1就足够了。 然后,进入构建稀疏表的第一阶段。 在遍历数组时,我们将标记或更新稀疏表上的值作为给定的数组元素。 然后嵌套,我们将遍历该数组,再次遍历k个行。 将i,j处的稀疏表更新为i,j-2处的稀疏表和i + XNUMX处的稀疏表之和J-1,j-1。 这将是稀疏表的最终必需更新。

对于给定为左,右范围的每个查询,我们需要遍历数组,但在此之前将输出值设置为0。将数组从16遍历为0,以便每次获得2的幂1 <

实施   

使用稀疏表进行范围总和查询的C ++程序

#include<iostream>

using namespace std;

const int k = 16;

const int N = 1e5;

long long sparse_table[N][k + 1];

void SparseTable(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        sparse_table[i][0] = arr[i];

    for (int j = 1; j <= k; j++)
        for (int i = 0; i <= n - (1 << j); i++)
            sparse_table[i][j] = sparse_table[i][j - 1] +
                                 sparse_table[i + (1 << (j - 1))][j - 1];
}

long long solveQuery(int Left, int Right)
{
    long long output = 0;
    for (int j = k; j >= 0; j--)
    {
        if (Left + (1 << j) - 1 <= Right)
        {
            output = output + sparse_table[Left][j];

            Left += 1 << j;
        }
    }
    return output;
}

int main()
{
    int arr[] = { 1,4,6,8,2,5 };
    int n = sizeof(arr) / sizeof(arr[0]);

    SparseTable(arr, n);

    cout << solveQuery(0, 3) << endl;
    cout << solveQuery(2, 4) << endl;
    cout << solveQuery(1, 5) << endl;

    return 0;
}
19
16
25

使用稀疏表进行范围总和查询的Java程序

class SumQueryRange
{
    static int k = 16;

    static int N = 100000;

    static long sparse_table[][] = new long[N][k + 1];

    static void SparseTable(int arr[],int n)
    {
        for (int i = 0; i < n; i++)
            sparse_table[i][0] = arr[i];

        for (int j = 1; j <= k; j++)
            for (int i = 0; i <= n - (1 << j); i++)
                sparse_table[i][j] = sparse_table[i][j - 1] + sparse_table[i + (1 << (j - 1))][j - 1];
    }
    
    static long solveQuery(int Left, int Right)
    {
        long sol = 0;
        for (int j = k; j >= 0; j--)
        {
            if (Left + (1 << j) - 1 <= Right)
            {
                sol = sol + sparse_table[Left][j];

                Left += 1 << j;
            }
        }
        return sol;
    }
    
    public static void main(String args[])
    {
        int arr[] = { 1,4,6,8,2,5};
        int n = arr.length;

        SparseTable(arr, n);

        System.out.println(solveQuery(0, 3));
        System.out.println(solveQuery(2, 4));
        System.out.println(solveQuery(1, 5));
    }
}
19
16
25

复杂度分析  

时间复杂度

O(n * log(n)) 哪里 “ n” 是数组中元素的数量。

参见
添加和搜索Word-数据结构设计LeetCode

空间复杂度

O(n * log(n)) 哪里 “ n” 是数组中元素的数量。

参考