All Tracks Data Structures Advanced Data Structures Fenwick (Binary Indexed) Trees Problem

Hacker with Team
/

Data Structures, Fenwick Tree, Fenwick tree

Problem
Editorial
Analytics

Alex has learnt many new concepts in hacking, and created his own team. He has N people (excluding Alex) in his team, where \(i^{th}\) person has individual skill value \(S_i\) where \(1 \le i \le N\). They are standing in a particular order, where \(1^{st}\) person being the leftmost person and \(N^{th}\) person being the rightmost person.

Alex has found a special way to evaluate the contribution done by each person in the team. Contribution done by \(i^{th}\) person (\(C_i\) ) in the team can be calculated as sum of his skill value and the skill values of his K adjacent team members on the left side, where the value of K will be decided by Alex.

In case, there are not enough members on the left side, contribution will be equal to the sum of his skill value and the skill values of all the team members on the left side.

Alternatively,
\(\space\space\space\space\space\) \(C_i\) = \(\sum_{j = maximum(i-K,1)}^{i } S_j\)

Alex can perform 2 types of operations now:

1) He can write a program to calculate the total contribution done by all the team members in the range of l to r (both inclusive), where contribution of each person will be calculated using value of K decided by him.

2) He can ask any person to change his skill value to X.

Being a great hacker, he is busy with other tasks, and needs your help in performing above operations.

Input Format:
First line contains 2 space-separated integers N and Q, where N denotes the number of people in Alex's team and Q denotes the number of operations Alex wants to get completed.

Second line contains N space-separated integers, where \(i^{th}\) integer denotes the skill value of \(i^{th}\) person in the team.

In next Q lines, each line contains first integer O, which represents the type of operation.

\(\space\) 1) For \(O=1\), line will contain 3 more space-separated integers \(l,r\) and K.
Here Alex wants to know the total contribution done by all team members in the range l to r (both inclusive), where contribution of each person will be calculated using value of K decided by him.

\(\space\) 2) For \(O=2\), line will contain 2 more space-separated integers i and X where Alex asks \(i^{th}\) person to change his skill value to X.

Output Format:

For each operation of the \(1^{st}\) type, print the required answer in the new line.

Constraints:

\(1 \le N,Q \le 10^5\)
\(1 \le S_i, X \le 10^8\)
\( 1 \le l \le r \le N\)
\( 1 \le K \le N\)

SAMPLE INPUT
6 3
1 2 3 4 5 6
1 4 5 2
2 4 3
1 4 5 2
SAMPLE OUTPUT
21
19
Explanation

Here \(N = 6\), and \(Q = 3\).

For first operation \(O=1\) and \(l = 4\) , \(r = 5\) and \(K= 2\). It means, we need to evaluate the contribution done by all the team members in the range \([4,5]\) with \(K=2\). Therefore:
\(C_4 = S_4 + S_3 + S_2 = 4 + 3 + 2 = 9 \)
\(C_5 = S_5 + S_4 + S_3 = 5 + 4 + 3 = 12 \)

So total contribution is \(21\).

For second operation \(O=2\), i.e \(4^{th}\) person will change his skill to 3, i.e \(S_4 = 3\).

For third operation, \(O=1\) and \(l = 4\) , \(r = 5\) and \(K= 2\). Now the required contribution will be \(19\).

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?