Data structure to answer queries

user_14282362 0
Viewed 70

Need some help in coming up with a data structure for answering this question. The objective is to perform Q queries of the following type on an array:

  1. Type 1: Given L and R, return \sum_{j = L to R} \sum_{k = j + 1 to R} (A_j * A_k)
  2. Type 2: Update position idx with a value val

How to answer these queries efficiently? The naive way is n^2. I was thinking along the lines of maintaining cumulative sum, since A_j factors out of the summation in the above equation.

math data-structures algorithm
2 Answers

This is what you are looking for.

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

user_92769960

Segment Tree, Fenwick Tree, and Square Root Decomposition are useful data structures to solve this kind of problem in better time complexity. (faster than n^2).

user_38260590
Related