Update array value for a given range

Question

they gave an array that initially had some value of Max.val, then there are queries making an update in Range L, R, so the value in any position is minimal. For instance:

Update Range 1 3 with value 3 Array 3 3 3 Max.val Max.val Now update 2 and 4 with 1 Array 3 1 1 1 Max.val Now update 1 and 2 with 2 Array 2 1 1 1 Max.val ie update only if(A[i]>value) A[i]=value; 

After the above request, I need to display the final array:ie 2 1 1 1 Max.val

I use the Segment Tree to resolve this issue, but I get TLE (time limit exceeded) . I do not know why? My approach is logN. Here is my update function

 public static void lets_change(int curr, int[] T, int x, int y, int a, int b, int c) { // x=0 and y=n and a=L , b=R and C= Value to be updated // T contains Integer.Max_value at start if (x > y || b < x || a > y) return; if (x == y) { T[curr] = Math.min(T[curr], c); return; } lets_change(2 * curr, T, x, (x + y) / 2, a, b, c); lets_change(2 * curr + 1, T, (x + y) / 2 + 1, y, a, b, c); T[curr] = Math.min(T[2 * curr], T[2 * curr + 1]); } 

Limitations:

 N<=10^5; Q<=10^5; 1<L<=R<=10^5 

What have I done wrong or is there a better way? Call function:

 for(int i=0;i<Q;i++){ int l = in.nextInt()-1; int r = in.nextInt()-1; int c = in.nextInt(); lets_change(1,T,0,n-1,l, r,c); } 

Answer 1

Your approach is not O (log n), because to upgrade from L to R you need to update all positions between L and R ( T[curr] = Math.min(T[curr], c) ).

In order to really get O (log n) updates, you have to implement a lazy segment tree. The essence of the structure is not to update each position. Whenever you come across a recursive update that spans the entire range, do not update immediately, just mark the node range, which will be updated later. And when updating (or requesting), distribute scheduled updates whenever necessary (when the request or update covers only part of the range and you need to go deeper).

Answer 2

You can do this in O (qlog (n)), where q is the number of requests.

The idea is to use BIT (binary indexed trees)

 // C++ program to demonstrate Range Update // and Range Queries using BIT #include <iostream> using namespace std; // Returns sum of arr[0..index]. This function assumes // that the array is preprocessed and partial sums of // array elements are stored in BITree[] int getSum(int BITree[], int index) { int sum = 0; // Initialize result // index in BITree[] is 1 more than the index in arr[] index = index + 1; // Traverse ancestors of BITree[index] while (index>0) { // Add current element of BITree to sum sum += BITree[index]; // Move index to parent node in getSum View index -= index & (-index); } return sum; } // Updates a node in Binary Index Tree (BITree) at given // index in BITree. The given value 'val' is added to // BITree[i] and all of its ancestors in tree. void updateBIT(int BITree[], int n, int index, int val) { // index in BITree[] is 1 more than the index in arr[] index = index + 1; // Traverse all ancestors and add 'val' while (index <= n) { // Add 'val' to current node of BI Tree BITree[index] += val; // Update index to that of parent in update View index += index & (-index); } } // Returns the sum of array from [0, x] int sum(int x, int BITTree1[], int BITTree2[]) { return (getSum(BITTree1, x) * x) - getSum(BITTree2, x); } void updateRange(int BITTree1[], int BITTree2[], int n, int val, int l, int r) { // Update Both the Binary Index Trees // As discussed in the article // Update BIT1 updateBIT(BITTree1,n,l,val); updateBIT(BITTree1,n,r+1,-val); // Update BIT2 updateBIT(BITTree2,n,l,val*(l-1)); updateBIT(BITTree2,n,r+1,-val*r); } int rangeSum(int l, int r, int BITTree1[], int BITTree2[]) { // Find sum from [0,r] then subtract sum // from [0,l-1] in order to find sum from // [l,r] return sum(r, BITTree1, BITTree2) - sum(l-1, BITTree1, BITTree2); } int *constructBITree(int n) { // Create and initialize BITree[] as 0 int *BITree = new int[n+1]; for (int i=1; i<=n; i++) BITree[i] = 0; return BITree; } // Driver Program to test above function int main() { int n = 5; // Construct two BIT int *BITTree1, *BITTree2; // BIT1 to get element at any index // in the array BITTree1 = constructBITree(n); // BIT 2 maintains the extra term // which needs to be subtracted BITTree2 = constructBITree(n); // Add 5 to all the elements from [0,4] int l = 0 , r = 4 , val = 5; updateRange(BITTree1,BITTree2,n,val,l,r); // Add 2 to all the elements from [2,4] l = 2 , r = 4 , val = 10; updateRange(BITTree1,BITTree2,n,val,l,r); // Find sum of all the elements from // [1,4] l = 1 , r = 4; cout << "Sum of elements from [" << l << "," << r << "] is "; cout << rangeSum(l,r,BITTree1,BITTree2) << "\n"; return 0; } 

An effective solution is to ensure that both requests can be executed in O (Log n). We get the amount of the amount using prefix amounts. How to make sure that the update is done so that the amount of the prefix can be completed quickly? Consider the situation when the prefix sum [0, k] (where 0 <= k <n) is necessary after updating the range in the range [l, r]. Three cases arise, since k can be in three regions.

Case 1: 0 <k <L The update request does not affect the amount request.

Case 2: l <= k <= r Consider an example:

Add 2 to the range [2, 4], the resulting array will be: 0 0 2 2 2 If k = 3 The sum of [0, k] = 4 How to get this result? Just add val from the lth index to the kth index. The amount increases by "val * (k) - val * (l-1)" after the update request.

Case 3: k> r For this case, we need to add "val" from the lth index to the rth index. The amount increases by "valr - val (l-1)" due to an update request.

Observations: Case 1: simple, as the amount will remain the same as before the update.

Case 2: the amount was increased by valk-val (l-1). We can find "val", it looks like searching for the ith element in updating a range and an article with query points. Thus, we support one BIT for Range and Point Queries updates, this BIT will be useful when searching for a value in the kth index. Now val * k is calculated, how to handle the additional term val * (l-1)? To cope with this extra deadline, we support another BIT (BIT2). Update val * (l-1) at the l-th index, so when getSum is executed on BIT2, the result will be obtained as val * (l-1).

Case 3: the sum in case 3 was increased by "val * r - val (l-1)", the value of this member can be obtained using BIT2. Instead of adding, we subtract "val (l-1) - valr", since we can get this value from BIT2 by adding val (l-1), as it was in case 2, and subtract val * r in each update operation.

 Update Query Update(BITree1, l, val) Update(BITree1, r+1, -val) UpdateBIT2(BITree2, l, val*(l-1)) UpdateBIT2(BITree2, r+1, -val*r) Range Sum getSum(BITTree1, k) *k) - getSum(BITTree2, k) 

Source: geeksforgeeks.org

Answer 3

 void lets_change(int curr, int T[] , int x, int y, int a, int b, int c) { if(lazy[curr] != inf ) { // This node needs to be updated T[curr] =min(T[curr], lazy[curr]); // Update it if(x != y) { lazy[curr*2] = min(lazy[2*curr],lazy[curr]); // Mark child as lazy lazy[curr*2+1] = min(lazy[2*curr+1],lazy[curr]); // Mark child as lazy } lazy[curr] = inf; // Reset it } if (x > y || b < x || a > y) return; if (x == y) { T[curr] = min(T[curr], c); return; } lets_change(2 * curr, T, x, (x + y) / 2, a, b, c); lets_change(2 * curr + 1, T, (x + y) / 2 + 1, y, a, b, c); T[curr] = min(T[2 * curr], T[2 * curr + 1]); } 

Here is my version lazy, it is in C ++. Add the lazy part to your query function and you will be good to go. If you need to access the entire array, you may need to redesign your query function.