高效的查询和更新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

查询1, 计算: A[L]x1+A[L+1]x2+......+A[R]x(R-L+1) + A[R] x (R - L+1)

查询2, 计算: A[L]x(R-L+1)+.+A[R-1]x2+A[R]x1。

查询3, 更新: A[X]=Y

输入:

N 和 Q，其中 N 是数组中元素的数量，而 Q 是查询次数。

下一行包含 N 的元素。

下一个 Q 行包含格式的查询。L R型

产出:

我们必须打印查询类型的结果 1 和 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;
                }
            }
        } 
    }

代码解释。

上面的代码是一个简单的粗暴的方法来计算查询的结果。第一类 和 二型我想不出任何算法或数据结构来优化查询结果。

代码时间复杂度。 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();