#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define ld long double
#define F first
#define S second
#define P pair<int,int>
#define pb push_back
#define max INT_MAX
void buildTree(int *a, int s , int e , int *tree, int index) {
//BASE CASE
if (s == e) {
tree[index] = a[s];
return;
}
//REC CASE
int mid = (s + e) / 2;
buildTree(a, s, mid, tree, 2 * index);
buildTree(a, mid + 1, e, tree, 2 * index + 1);
tree[index] = min(tree[2 * index], tree[2 * index + 1]);
return;
}
int query(int *tree, int ss, int se, int qs, int qe, int index) {
if (ss >= qs && se <= qe) {
return tree[index];
}
if (qe < ss || qs > se) {
return max;
}
int mid = (ss + se) / 2;
int leftAns = query(tree, ss, mid, qs, qe, 2 * index);
int rightAns = query(tree, mid + 1, se, qs, qe, 2 * index + 1);
return min(leftAns, rightAns);
}
void updateNode(int *tree, int ss, int se, int i, int update, int index) {
if (i > se || i < ss) {
return;
}
if (ss == se) {
// COUT UPDATE INFORMATION-1
// cout << "index: " << ss << endl;
// cout << tree[index] << "==>";
tree[index] += update;
// COUT UPDATE INFORMATION-2
// cout << tree[index] << endl;
return;
}
int mid = (ss + se) / 2;
updateNode(tree, ss, mid, i, update, 2 * index);
updateNode(tree, mid + 1, se, i, update, 2 * index + 1);
}
void updateRange(int *tree, int ss, int se, int l, int r, int update, int index ) {
if (l > se || r < ss) {
return;
}
if (ss == se) {
// COUT UPDATE INFORMATION-1
cout << "index: " << ss << endl;
cout << tree[index] << "==>";
tree[index] = update;
// COUT UPDATE INFORMATION-2
cout << tree[index] << endl;
return;
}
int mid = (ss + se) / 2;
updateRange(tree, ss, mid, l, r, update, 2 * index);
updateRange(tree, mid + 1, se, l, r, update, 2 * index + 1);
tree[index] = min(tree[2 * index], tree[2 * index + 1]);
return;
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base:: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
// int t;cin>>t;while(t--)
{
int j, k, m, ans = 0, cnt = 0, sum = 0, update, indexToUpdate, left, right, no_of_query, queryLeft, queryRight;
int n;
cin >> n >> no_of_query;
int a[n];
//ARRAY HAVE ZERO BASED INDEXING
//TREE HAVE ONE BASED INDEXING
for (int i = 0; i < n; ++i)
{
cin >> a[i];
}
//INITIALISING TREE WITH ZERO
int tree[4 * n + 1] = {0};
//BUILDTREE(ARRAY, START, END, TREE, TREE-STARTING-INDEX)
buildTree(a, 0, n - 1, tree, 1);
//COUT TREE
// for (int i = 1; i <= (4 * n + 1); ++i)
// {
// cout << tree[i] << " ";
// }
// cout<<endl;
//UPDATE TREE NODE
{
// cin >> indexToUpdate >> update;
//UPDATENODE(TREE, ARRAY-STARTING, ARRAY-ENDING, INDEX-WHERE-UPDATE, UPDATE, TREE-STARTING-INDEX)
// updateNode(tree, 0, n - 1, indexToUpdate, update, 1);
}
//UPDATE TREE RANGE
{
// cin >> left >> right >> update;
//UPDATERANGE(TREE, TREE-START, TREE-END, RANGE-START, RANGE-END, UPDATE, TREE-STARTING-INDEX)
// updateRange(tree, 0, n - 1, left, right, update, 1);
}
//QUERY
{
int type;
while (no_of_query--) {
cin >> type >> queryLeft >> queryRight;
if (type == 1) {
//QUERY(TREE, ARRAY-START, ARRAY-END, QUERY-LEFT, QUERY-RIGHT, TREE-STARTING-INDEX)
cout << query(tree, 0, n - 1, queryLeft - 1, queryRight - 1, 1) << endl;
}
else {
indexToUpdate = queryLeft;
update = queryRight;
// UPDATENODE(TREE, ARRAY - STARTING, ARRAY - ENDING, INDEX - WHERE - UPDATE, UPDATE, TREE - STARTING - INDEX)
updateNode(tree, 0, n - 1, indexToUpdate - 1, update, 1);
}
}
}
}
}
What is wrong with this code
hello Himanshu,
In ur updated function u are not updating tree after second update call.
after the last update call u should update ur tree something as ->
tree[index]=min( tree[2 * index] , tree[2 * index+1] )
please share question as well ,i will check.
also please press the save button and share the link again
1 Like
You are given an array A of n elements and Q queries. Each query can be of following types:
1 L R: Print the minimum value in AL, AL+1, AL+2….,AR.
2 X Y: Update the value of Ax with Y.
Input Format
First line contains integers N and Q, denoting the number of elements and number of queries. Next line contains N integers, denoting A1, A2, A3….,AN. Next Q lines contains Q queries.
Constraints
1<=N,Q<=10^5 |Ai|,|Y|<=10^9 1<=L,R,X<=N
Output Format
Answer each query of type 1.
Sample Input
5 5
1 4 3 5 2
1 1 5
2 3 9
1 2 4
1 2 5
1 3 4
Sample Output
1
4
2
5
Yeah, this was the result of yesterday’s experimentation. I changed some code in hope of it will work and forgot to revert it. thanks
