Cho một mảng arr [m] với m số nguyên và n, là giá trị được thêm vào một mảng và r truy vấn được đưa ra với một số bắt đầu và kết thúc. Đối với mỗi truy vấn, chúng ta phải thêm giá trị n từ đầu đến cuối giới hạn trong một mảng.
Ví dụ
Input:
arr[] = {1, 2, 3, 4, 5}
query[] = { { 0, 3 }, { 1, 2 } }
n = 2
Output:
If we run above program then it will generate following output:
Query1: { 3, 4, 5, 6, 5 }
Query2: { 3, 6, 7, 6, 5 } Chương trình này có thể được giải quyết bằng một cách tiếp cận dễ dàng, trong đó -
- Chúng tôi sẽ lặp lại tất cả các truy vấn đi qua mảng bắt đầu từ điểm bắt đầu trong truy vấn và cho đến điểm kết thúc được lưu trữ trong truy vấn.
- Thêm giá trị của n và in mảng.
Thuật toán
START STEP 1 : DECLARE A STRUCT range for start AND end LIMITS STEP 2 : IN FUNCTION add_tomatrix(int arr[], struct range r[], int n, int size, int m) int i, j, k; LOOP FOR i = 0 AND i < m AND i++ LOOP FOR j = r[i].start AND j<= r[i].end AND j++ arr[j] = arr[j] + n END FOR LOOP FOR k = 0 AND k < size AND k++ PRINT arr[k] END FOR END FOR STOP
Ví dụ
#include <stdio.h>
struct range{
int start, end; //struct to give the range for the array elements
};
int add_tomatrix(int arr[], struct range r[], int n, int size, int m){
int i, j, k;
for ( i = 0; i < m; i++) //for all the elements in a struct we defined{
for(j = r[i].start; j<= r[i].end; j++) //from where till where we want our results to be updated{
arr[j] += n; //add the value of the particular range
}
printf("Query %d:", i+1);
for ( k = 0; k < size; k++){
printf(" %d",arr[k]); // print the whole array after every query
}
printf("\n");
}
}
int main(int argc, char const *argv[]){
int arr[] ={3, 4, 8, 1, 10};
struct range r[] = {{0,2}, {1, 3}, {3, 4}};
int n = 2;
int size = sizeof(arr)/sizeof(arr[0]);
int m = sizeof(r)/sizeof(r[0]);
add_tomatrix(arr, r, n, size, m);
return 0;
} Đầu ra
Nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra kết quả sau -
Query 1: 5 6 10 1 10 Query 2: 5 8 12 3 10 Query 3: 5 8 12 5 12