Summary:
This problem mainly uses the single point modification of the line segment tree and the operation of interval summation.
Or use the interval summation operation of the tree array
Title Link: https://acm.hdu.edu.cn/showproblem.php?pid=1166
Title:
Problem Description
Country A, the sworn enemy of country C, is conducting military exercises these days, so Derek, the spy leader of country C, and his Tidy are busy again. Country A has arranged N engineering camps along A straight line along the coastline. Derek and Tidy's task is to monitor the activities of these engineering camps. Due to the adoption of some advanced monitoring means, the number of people in each engineering camp is well known in country C. the number of people in each engineering camp may change, and some people may be increased or reduced, but these can not escape the monitoring of country C.
The CIA needs to study what tactics the enemy is practicing, so tidy should report to Derek at any time how many people there are in a continuous engineering camp. For example, Derek asked, "tidy, report immediately how many people there are from the third camp to the tenth camp!" Tidy is about to start counting the total number of people in this section and report it. However, the number of enemy soldiers in the camp often changes, and Derek's paragraphs are different every time, so tidy had to count one camp at a time, and she was soon exhausted, Derek is more and more dissatisfied with tidy's calculation speed: "you dead fat boy, if you calculate so slowly, I'll fire you!" tidy thought: "calculate it yourself. It's really a tiring job! I can't wait for you to fire me!" In desperation, tidy had to call windbreaker, a computer expert, for help. Windbreaker said, "dead fat boy, I told you to do more acm problems and read more algorithm books. Now you have tasted the bitter fruit!" Tidy said, "I know I'm wrong..." But windbreaker has hung up. Tidy is very upset. He will really collapse. Smart reader, can you write a program to help him finish the work? However, if your program is not efficient enough, tedy will still be scolded by Derek
Input
The first line is an integer T, indicating that there are t groups of data.
The first row of each group of data has a positive integer N (N < = 50000), indicating that the enemy has N engineering camps, followed by N positive integers. The i positive integer ai represents that there are ai individuals at the beginning of the i engineering camp (1 < = ai < = 50).
Next, there is a command on each line. The command has four forms:
(1) Add i, J, i and j are positive integers, indicating that J people are added in the ith camp (J does not exceed 30)
(2) Sub i, J, i and j are positive integers, indicating the reduction of J persons in the ith camp (J does not exceed 30);
(3) Query i, J, i and j are positive integers, i < = J, indicating the total number of people from the i to j camps;
(4)End means end, and this command appears at the end of each group of data;
There are up to 40000 commands per group of data
Output
For group i data, first output "Case i:" and enter,
For each Query query, output an integer and enter to represent the total number of people in the Query segment, which should be kept within int.
Sample Input
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End
Sample Output
Case 1:
6
33
59
Analysis 1: segment tree
This problem can be solved by using line segment tree,
The node structure is:
struct Node
{
int l,r;
int sum; // This is the answer to maintenance
}
You only need to use push up, modify, build and query operations.
During build(), the value will be initialized first in the process of building the tree.
Push up updates the sum value of the parent node through the child node.
Code implementation:
# include <iostream>
# include <stdio.h>
using namespace std;
const int N = 50010;
struct Node
{
int l,r;
int sum;
}edgs[N * 4];
int a[N];
void pushup(int u)
{
edgs[u].sum = edgs[2 * u].sum + edgs[2 * u + 1].sum;
}
void build(int u , int l ,int r)
{
edgs[u].l = l,edgs[u].r = r;
if(l == r)
{
edgs[u].sum = a[l];
}
else
{
int mid = (edgs[u].l + edgs[u].r) / 2;
build(2 * u , l , mid);
build(2 * u +1 , mid +1 , r);
pushup(u);
}
}
void modify(int u , int x , int v)
{
if(edgs[u].l == x && edgs[u].r == x)
{
edgs[u].sum += v;
return;
}
else
{
int mid = (edgs[u].l + edgs[u].r) / 2;
if(x <= mid)
{
modify(2 * u , x , v);
}
else
{
modify(2 * u + 1 , x , v);
}
pushup(u);
}
}
int query(int u , int l , int r)
{
if(edgs[u].l >= l && edgs[u].r <= r)
{
return edgs[u].sum;
}
int total = 0;
int mid = ( edgs[u].l + edgs[u].r ) / 2;
if(l <= mid)
{
total += query(2 * u , l , r);
}
if(r > mid)
{
total += query(2 * u + 1 , l , r);
}
return total;
}
int main()
{
int t;
scanf("%d",&t);
for(int j = 1 ; j <= t ; j++)
{
printf("Case %d:\n",j);
int n;
scanf("%d",&n);
for(int i = 1 ; i <= n ; i++)
{
scanf("%d",&a[i]);
}
build(1,1,n);
string ch;
while(cin >> ch)
{
if(ch == "End")
{
break;
}
else if(ch == "Query")
{
int l,r;
scanf("%d %d",&l,&r);
printf("%d\n",query(1,l,r));
}
else if(ch == "Add")
{
int t,v;
scanf("%d %d",&t,&v);
modify(1,t,v);
}
else
{
int t,v;
scanf("%d %d",&t,&v);
modify(1,t,-v);
}
}
}
}Analysis 2: tree array
The tree array is used to maintain the prefix and to facilitate single point modification and interval summation.
Just use the template.
Code implementation:
# include <iostream>
# include <stdio.h>
# include <string>
# include <cstring>
using namespace std;
const int N = 50010;
int t[N];
int n;
int lowbit(int x)
{
return x & -x;
}
void modify(int idx , int v)
{
for(int i = idx ; i <= n ; i += lowbit(i))
{
t[i] += v;
}
}
int query(int idx) // Find the value of 1~idx
{
int res = 0;
for(int i = idx ; i ; i -= lowbit(i))
{
res += t[i];
}
return res;
}
int main()
{
int loop;
scanf("%d",&loop);
for(int j = 1; j <= loop ; j++)
{
memset(t,0,sizeof t);
printf("Case %d:\n",j);
scanf("%d",&n);
for(int i = 1 ; i <= n ; i++)
{
int temp;
scanf("%d",&temp);
modify(i,temp);
}
string ch;
while(cin >> ch)
{
if(ch == "End")
{
break;
}
else if(ch == "Query")
{
int l,r;
scanf("%d %d",&l,&r);
printf("%d\n",query(r) - query(l - 1)); // Value of l~r
}
else if(ch == "Add")
{
int x , v;
scanf("%d %d",&x,&v);
modify(x,v);
}
else
{
int x,v;
scanf("%d %d",&x,&v);
modify(x,-v);
}
}
}
return 0;
}