CODEWITHSUNDEEP
algorithmsortingsegment-treebinary-indexed-tree
piedpiper
piedpiper

Reputation: 1360

How can we calculate weighted cumulative sum of squares with prefix range updates by one?

Given an array A with n elements which starts with all 0s and another array W also with n elements (all greater than 0), we want to perform the following operation repeatedly;

For a given k, increment A[0], A[1], .... A[k] each by 1, and report the value of A[0]^2 * W[0] + A[1]^2 * W[1] + ... + A[n-1]^2 * W[n-1].

Looking for an O(log n) solution (per query), or faster.

Upvotes: 3

Views: 265

Answers (0)

Related Questions