**Array Manipulation**

### Problem Statement :

Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the values of k between the indices a and b inclusive: index-> 1 2 3 4 5 6 7 8 9 10 [0,0,0, 0, 0,0,0,0,0, 0] [3,3,3, 3, 3,0,0,0,0, 0] [3,3,3,10,10,7,7,7,0, 0] [3,3,3,10,10,8,8,8,1, 0] The largest value is 10 after all operations are performed. Function Description: Complete the function arrayManipulation in the editor below. arrayManipulation has the following parameters: i 1. nt n - the number of elements in the array 2.int queries[q][3] - a two dimensional array of queries where each queries[i] contains three integers, a, b, and k. Returns: 1. int - the maximum value in the resultant array Input Format: The first line contains two space-separated integers n and m, the size of the array and the number of operations. Each of the next lines contains three space-separated integers a, b and k, the left index, right index and summand. Constraints: 1. 3<=n<=10^7 2. 1<=m<=2*10^5 3. 1<=a,b<=n 4. 0<=k<=10^9

### Solution :

` ````
Solution in C :
In C:
#include <stdio.h>
long long arr[10000005];
long long diff[10000005];
int main(void)
{
int a,b,k,n,m,i;
long long max,val;
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d%d",&a,&b,&k);
if(a==1)
{
arr[1] += k;
if(b<n)
diff[b] -= k;
}
else if(b<n)
{
diff[a-1] += k;
diff[b] -= k;
}
else if(b==n)
diff[a-1] += k;
}
max = arr[1];
val = arr[1];
for(i=1;i<n;i++)
{
val += diff[i];
if(val > max)
max = val;
}
printf("%lld\n",max);
return 0;
}
In C++:
#include <iostream>
using namespace std;
const int NMAX = 1e7+2;
long long a[NMAX];
int main()
{
int n, m;
cin >> n >> m;
for(int i=1;i<=m;++i){
int x, y, k;
cin >> x >> y >> k;
a[x] += k;
a[y+1] -= k;
}
long long x = 0,sol=-(1LL<<60);
for(int i=1;i<=n;++i){
x += a[i];
sol = max(sol,x);
}
cout<<sol<<"\n";
return 0;
}
In Java:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Solution {
public static void main(String[] args) throws Exception {
new Solution().run();
}
StreamTokenizer st;
private void run() throws Exception {
st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
int n = nextInt();
int m = nextInt();
long[] a = new long[n + 1];
for (int i = 0; i < m; i++) {
int l = nextInt() - 1;
int r = nextInt();
int v = nextInt();
a[l] += v;
a[r] -= v;
}
long cur = 0;
long max = 0;
for (int i = 0; i < n; i++) {
cur += a[i];
max = Math.max(max, cur);
}
System.out.println(max);
}
private int nextInt() throws Exception {
st.nextToken();
return (int) st.nval;
}
}
In Python 3:
N,M = [int(_) for _ in input().split(' ')]
Is = {}
for m in range(M) :
a,b,k = [int(_) for _ in input().strip().split(' ')]
if k == 0 :
continue
Is[a] = Is.get(a,0) + k
Is[b+1] = Is.get(b+1,0) - k
m,v = 0,0
for i in sorted(Is) :
v += Is[i]
if v > m :
m = v
print(m)
```

## View More Similar Problems

## Tree: Preorder Traversal

Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's

View Solution →## Tree: Postorder Traversal

Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the

View Solution →## Tree: Inorder Traversal

In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func

View Solution →## Tree: Height of a Binary Tree

The height of a binary tree is the number of edges between the tree's root and its furthest leaf. For example, the following binary tree is of height : image Function Description Complete the getHeight or height function in the editor. It must return the height of a binary tree as an integer. getHeight or height has the following parameter(s): root: a reference to the root of a binary

View Solution →## Tree : Top View

Given a pointer to the root of a binary tree, print the top view of the binary tree. The tree as seen from the top the nodes, is called the top view of the tree. For example : 1 \ 2 \ 5 / \ 3 6 \ 4 Top View : 1 -> 2 -> 5 -> 6 Complete the function topView and print the resulting values on a single line separated by space.

View Solution →## Tree: Level Order Traversal

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function levelOrder and print the values in a single line separated by a space. For example: 1 \ 2 \ 5 / \ 3 6 \ 4 F

View Solution →