查询和更新 A[L]*1 + A[L+1]*2 ... + A[R]*(R-L+1) 的高效方式

Question

给定一个数组A[N]，要求我们对给定的数组执行以下3种类型的查询数组：

1 L R

2 L R

3 X Y

Query 1, Calculate: A[L] x 1 + A[L + 1] x 2 + ........ + A[R] x (R - L+ 1)

Query 2, Calculate: A[L] x (R - L + 1) +..........+ A[R - 1] x 2 + A[R] x 1

Query 3, Update: A[X] = Y

输入:

N and Q, where N is the number of elements in the array, and Q is the number of queries.

The next line contains N elements of the array.

Next Q lines contain queries in the format: type L R

输出:

We have to print results for query types 1 and 2.

约束条件:

1 <= N, Q <= 10^5

1 <= L <= R <= N

1 <= A[i] <= 10^9

示例测试用例:

Inputs:

5 4
1 2 3 4 5
1 1 2
2 1 2
3 2 1
1 1 2

Output:
5
4
3

 import java.util.*;

    public class TestClass {

        public static void main(String[] args) {
            Scanner scn = new Scanner(System.in);
            int n = scn.nextInt();   
            int q = scn.nextInt();
            int[] arr = new int[n];

            for (int i = 0; i < n; i++) {
                arr[i] = scn.nextInt();
            }

            while (q-- > 0) {
                int type = scn.nextInt();    // type is for which type of query user enters.
                int l = scn.nextInt();
                int r = scn.nextInt();       
                long ans = 0;                   // ans variable i take it in long as answer may be grater.
                if (type == 1) {      
                    int count = 1;
                    while (l <= r) {
                        ans = ans + arr[l - 1] * count;  //Also in this array is started with index 1 not with 0 that means 0 index element is first element.
                        count++;
                        l++;
                    }
                    System.out.println(ans);  //Printing answer for query1.
                } else if (type == 2) {
                    int count = (r - l + 1);
                    while (l <= r) {
                        ans = ans + arr[l - 1] * count;
                        count--;
                        l++;
                    }
                    System.out.println(ans);  // Printing answer here for query 2.
                } else if (type == 3) {   
                    arr[l - 1] = r;
                }
            }
        } 
    }

代码解释：

以上代码是计算查询结果的简单暴力方法type 1 and type 2，我想不出有什么算法或者数据结构来优化查询的结果。

代码时间复杂度： O(Q x N)

根据约束，看起来我们必须在 O( sqrt(N ) ) 或 O( log(N) ) 次。

我们如何优化类型 1 和类型 2 查询？

Answer 1

假设我们有值：

0 1 2 3 4 (indexes)
a b c d e

a + 2b + 3c + 4d + 5e = S

计算 [1, 3] 的查询 1（从零开始）：

S - a - 5e - (b + c + d)

计算 [2, 4] 的查询 1（从零开始）：

S - (a + 2b) - (2c + 2d + 2e)

所以这些类型的查询可以在 O(1) 中通过预处理得到回答。我们需要两个结构：一个存储常规前缀和：

[1, 2, 3, 4, 5]
[1, 3, 6, 10, 15]

另一个带乘数的：

[1, 2, 3, 4, 5]
[1, 5, 14, 30, 55]

由于我们还需要修改前缀和，所以我们可以对每种前缀和使用一个线段树，然后在O(log n)时间查询和更新。

JavaScript代码：

// Adapted from https://codeforces.com/blog/entry/18051
function build(t, n) {  // build the tree
  for (let i = n - 1; i > 0; --i) t[i] = t[i<<1] + t[i<<1|1];
}

function modify(t, p, value, n) {  // set value at position p
  for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = t[p] + t[p^1];
}

function query(t, l, r, n) {  // sum on interval [l, r)
  let res = 0;
  for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
    if (l&1) res += t[l++];
    if (r&1) res += t[--r];
  }
  return res;
}
// End adaptation from https://codeforces.com/blog/entry/18051


function main() {
  var A = [1,2,3,4,5];
  var Qs = [
    [1, 1, 2],
    [2, 1, 2],
    [3, 2, 1],
    [1, 1, 2]
  ];

  const n = A.length;
  const t0 = new Array(2 * (n + 1)).fill(0);
  const t1 = new Array(2 * (n + 1)).fill(0);
  const t2 = new Array(2 * (n + 1)).fill(0);

  // Build segment trees
  for (let i = 0; i < A.length; i++){
    t0[n + i] = A[i];
    t1[n + i] = (i + 1) * A[i];
    t2[n + i] = (n - i) * A[i];
  }
  build(t0, n);
  build(t1, n);
  build(t2, n);

  for (let [type, lx, ry] of Qs){
    // Adjust for non-zero-based indexes
    lx = lx - 1;
    ry = ry - 1;

    if (type == 1){
      let S = query(t1, 0, n + 1, n);
      let left = query(t1, 0, lx, n);
      let right = query(t1, ry + 1, n + 1, n);
      let subtrahend = lx * query(t0, lx, ry + 1, n);
      console.log(S - left - right - subtrahend);
    
    } else if (type == 2){
      let S = query(t2, 0, n + 1, n);
      let left = query(t2, 0, lx, n);
      let right = query(t2, ry + 1, n + 1, n);
      let subtrahend = (n - ry - 1) * query(t0, lx, ry + 1, n);
      console.log(S - left - right - subtrahend);

    } else {
      ry = ry + 1;
      modify(t0, lx, ry, n);
      modify(t1, lx, ry * (lx + 1), n);
      modify(t2, lx, ry * (n - lx), n);
    }
  }
}

main();