c++ - 分段求和算法

Question

我正在尝试解决以下任务:

1) 给定大小为N的数组A。
2) 给定一组范围更新查询，即 (L, R, val) 应该为 L <= i <= R 执行 A[i] += val。< br/>3) 给定一组range sum 查询，即 (L, R) 应该为 L <= i <= R 返回 sum(A[i])。

约束:

1) A、段和查询集的大小 N、N1、N2 <= 2^24。
2) 0 <= L <= 2^24, 0 <= R <= 2^24, 0 <= val <= 2^24。

问题是计算所有范围求和查询的总和 (S) 模 2^32。

似乎可以实现线段树以用O(NlogN)时间获得所需的总和，但实际上我们没有 需要用到这个数据结构。相反，我们可以仅使用 2 或 3 个数组以某种方式在 O(N) 时间内计算出 S。这里的总体思路是什么？

我最近用 C++ 写了一些算法来解决这个问题，但这不是最优的。伪代码:

1. 创建两个数组 Add[0..N-1] 和 Substract[0..N-1]。
   
2. 迭代范围更新集并执行 Add[L] += val 和 Substract[R] += val。
   
3. 创建数组 Partial_sum[0..N]
   
4. Partial_sum[0] = 0，what_to_add = 0。
   
5. 对于 [1..N] 中的 i:
   5.1. Partial_sum[i] = Partial_sum[i - 1] + Add[i - 1] + what_do_add
   5.2. what_do_add = what_to_add + 添加[i - 1] - 减去[i - 1]

我们得到 Partial_sum 数组，并且可以像 Partial_sum[R+1] 一样在 O(1) 时间内轻松计算任何段和 (L, R) - Partial_sum[L]。

但是，问题是第 2 步太慢了。另外，第 5 步中的循环很难理解。这是 O(n) 解决方案，但常数太高。我知道应该有改进第 5 步的方法，但我不知道该怎么做。

有人可以提供一些想法甚至建议他们自己的算法来解决这个问题吗？

谢谢。

我的算法实现:

#include <cstring>
#include <iostream>
#include <stdio.h>

typedef unsigned int UINT;
typedef unsigned long long ULL;


//MOD and size of A
const ULL MOD  = 4294967296LL; // 2^32
const size_t N = 16777216;     // 2^24

//params for next_rand()
UINT seed = 0;
UINT a;
UINT b;


//get random segment
UINT next_rand()
{
    seed = seed * a + b;
    return seed >> 8;
}


int main()
{
    UINT N1, N2;

    std::cin >> N1 >> N2;
    std::cin >> a >> b;

    UINT* add  = new UINT[N];         //Add array
    UINT* subs = new UINT[N];         //Substraction array
    UINT* part_sum = new UINT[N + 1]; //Partial sums array

    memset(add, 0, sizeof(UINT) * N);
    memset(subs, 0, sizeof(UINT) * N);
    memset(part_sum, 0, sizeof(UINT) * (N + 1));  //Initialize arrays

    //step 2 
    for (size_t i = 0; i < N1; ++i)
    {
        UINT val = next_rand();
        UINT l   = next_rand();
        UINT r   = next_rand();

        if (l > r)
        {
            std::swap(l, r);
        }

        add[l]  = (add[l] + val);
        subs[r] = (subs[r] + val);
    }

    part_sum[0]   = 0;
    UINT curr_add = 0;

    //step 5
    for (size_t i = 1; i <= N; ++i)
    {
        part_sum[i] = (part_sum[i - 1] + curr_add + add[i - 1]);

        curr_add = (curr_add + add[i - 1] - subs[i - 1]);
    }

    UINT res_sum = 0;

    //Get any segment sum in O(1)
    for (size_t i = 0; i < N2; ++i)
    {
        UINT l = next_rand();
        UINT r = next_rand();

        if (l > r)
        {
            std::swap(l, r);
        }
        res_sum = (res_sum + part_sum[r + 1] - part_sum[l]);
    }

    std::cout << res_sum;

    delete []add;
    delete []subs;
    delete []part_sum;

    return 0;
}

Answer 1

我以不同的方式实现了所描述的算法。它应该工作得更快。在更新和求和查询大小的最大值下，它应该比以前工作得更快。

#include <iostream>
#include <stdio.h>
#include <vector>

typedef unsigned int UINT;
typedef unsigned long long ULL;

const ULL MOD  = 4294967296LL; // 2^32
const size_t N = 16777216;     // 2^24

UINT seed = 0;
UINT a;
UINT b;

UINT next_rand()
{
    seed = seed * a + b;

    return seed >> 8;
}

std::vector <std::pair<UINT, UINT> > add;

int main()
{
    UINT upd_query_count;
    UINT sum_query_count;

    // freopen("fastadd.in",  "r", stdin);
    // freopen("fastadd.out", "w", stdout);

    scanf("%u", &upd_query_count);
    scanf("%u", &sum_query_count);
    scanf("%u", &a);
    scanf("%u", &b);

    add.reserve(N+1);

    for (size_t i = 0; i < upd_query_count; ++i)
    {  
        UINT val = next_rand();
        UINT l   = next_rand();
        UINT r   = next_rand();

        if (l > r)
        {
            add[r].first     += val;
            add[l + 1].first -= val;
        }
        else
        {
            add[l].first     += val;
            add[r + 1].first -= val;
        }
    }

    for (size_t i = 0; i < sum_query_count; ++i)
    {
        UINT l = next_rand();
        UINT r = next_rand();

        if (l > r)
        {
            ++add[r].second;
            --add[l + 1].second;
        }
        else
        {
            ++add[l].second;
            --add[r + 1].second;
        }
    }

    UINT curr_add = 0;
    UINT res_sum  = 0;
    UINT times    = 0;

    for (size_t i = 0; i < N; ++i )
    {
        curr_add += add[i].first;
        times    += add[i].second;

        res_sum += curr_add * times;
    }

    printf("%u\n", res_sum);

    return 0;
}