___Abc123___'s blog

Help Needed
By ___Abc123___, history, 4 months ago, In English

Hi, Here is the Question You are given an array A of length N and q queries where each query is one of the following types:

1 i val: Update the value at ith index to val (arr[i] = val)

   2 L R: find the sum of all the subarray of arr[L....R]

Determine the value of query 2 Ex: N = 5

q 2;

arr = [2, 1, 4, 3, 1]

query = [(1, 2, 2), (2, 1, 3)]

Output = 26

How to approach this question

I have to find sum of every subarray of arr[L...R] ans will be arr[L] + arr[L...(L + 1)] + arr[L...(L +2)] +.....arr[L....R] + arr[L + 1] + (arr(L + 1)..(L + 2)] +.....(arr[(L + 1)...R])......

constraint 1 <= N, q <= 100000

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ___Abc123___ (previous revision, new revision, compare).

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

is this not just a standard seg/fenwick tree problem try learning one of these datastructures, then it will be a template problem

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Check https://leetcode.com/problems/range-sum-query-mutable/description/.

People there have given great explanations for this problem already.

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have to find sum of every subarray of arr[L...R] ans will be arr[L] + arr[L...(L + 1)] + arr[L...(L +2)] +.....arr[L....R] + arr[L + 1] + (arr(L + 1)..(L + 2)] +.....(arr[(L + 1)...R])......

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    interestingly i have actually seen this problem before

    try thinking about it as how many times each element in the range contributes to the final sum

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes I have done that final expression will be (r — l + 1)arr[l] + 2*(r — l)arr[l + 1] + 3*(r — l — 1)*arr[l + 2]+.....+(r — l + 1)arr[r].

      still cant figure out what to do from here

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Another way to look at it would be to only check the contribution of each individual element in $$$[L,R]$$$. Here the $$$ith$$$ elements contribution would be $$$arr[i]*(r-i+1)*(i-l+1)$$$ as these many subarrays in $$$[L,R]$$$ contain it. Now you can see that you only need the sum of $$$arr[i]*i, arr[i]*i*i, arr[i]$$$ to find the contribution of all elements which you can find using a segment tree.

        → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        heres the soltuion

        you precompute an array containing the values arr[I] = nums[I] * (n-i)

        now build a segtree on arr, for each query you would just query the sum between l and r and the sum from r+1 to the end

        subtract the sum between r+1 to n from l and r and you get the answer to your query this works cuz math

        → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ___Abc123___ (previous revision, new revision, compare).

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Click Here

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Try learning about Fenwick Tree(Binary Indexed Tree) or Segment trees! :)

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

this can be solved using Segment trees in a fast time Click on this and go learn it

→ Reply