The question : Interval and

Ideas : Line segment tree

#include<iostream>
#include<stdio.h>
using namespace std; #define MAXN 50005
int ans; struct node{
int left,right,sum;
int mid(){
return (left+right)>>;
}
}tree[MAXN*];// Pay attention to the scope ,4 Times the space void btree(int left,int right,int rt){// Build up trees
tree[rt].left=left;
tree[rt].right=right;
if(left==right){
scanf("%d",&tree[rt].sum);
return;
}
int mid=tree[rt].mid();
btree(left,mid,rt<<);
btree(mid+,right,rt<<|);
tree[rt].sum=tree[rt<<].sum+tree[rt<<|].sum;// The number of points in the interval = Left interval + The right range
} void query(int left,int right,int rt,int L,int R){// Ask and sum
if(L<=left&&right<=R){
ans+=tree[rt].sum;
return;
}
int mid=tree[rt].mid();
if(R<=mid)query(left,mid,rt<<,L,R);// The interval is in the left subtree
else if(L>mid)query(mid+,right,rt<<|,L,R);// The interval is in the right subtree
else{
query(left,mid,rt<<,L,R);
query(mid+,right,rt<<|,L,R);
}
} void update(int left,int right,int rt,int pos,int add){// Single point update function
if(left==right){
tree[rt].sum+=add;
return;
}
int mid=tree[rt].mid();
if(pos<=mid)update(left,mid,rt<<,pos,add);// The point is in the left subtree
else update(mid+,right,rt<<|,pos,add);// It's on the right subtree
tree[rt].sum=tree[rt<<].sum+tree[rt<<|].sum;// Interval and update
} int main(){
int t,n,a,b,i;
char str[];
scanf("%d",&t);
for(i=;i<=t;++i){
printf("Case %d:\n",i);
scanf("%d",&n);
btree(,n,);
while(~scanf("%s",str)&&str[]!='E'){
scanf("%d%d",&a,&b);
if(str[]=='A')update(,n,,a,b);
else if(str[]=='S')update(,n,,a,-b);
else{
ans=;
query(,n,,a,b);
printf("%d\n",ans);
}
}
}
return ;
}

hdu 1166 The enemy troops were arrayed ( Single point update of segment tree , Interval query ) More articles about

  1. HDU.1166 The enemy troops were arrayed ( Line segment tree Single point update Interval query )

    HDU.1166 The enemy troops were arrayed ( Line segment tree Single point update Interval query ) Problem analysis Deepen the understanding , Rewrite it Code Overview #include <bits/stdc++.h> #define nmax 100000 ...

  2. HDU 1166 The enemy troops were arrayed ( Single point update of segment tree , Board question )

    The enemy troops were arrayed Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submi ...

  3. HDU 1166 The enemy troops were arrayed ( Single point update of segment tree )

    The enemy troops were arrayed There are some differences between single point update and interval update , It should be noted ! [ Topic link ] The enemy troops were arrayed [ Topic type ] Single point update of segment tree & The question : The first line is an integer T, Express T Group data . The first row of each group of data is a positive integer N(N< ...

  4. HDU 1166 The enemy troops were arrayed ( Single point update of segment tree , Interval query )

    describe C The enemy of our country A China is conducting military exercises during this period , therefore C The head of the country Derek And his men Tidy I'm busy again .A Our country is in a straight line along the coastline N An engineering camp ,Derek and Tidy My task is to monitor the activities of these engineering camps ...

  5. HDU 1166 The enemy troops were arrayed &lt; Line segment tree Single point modification Interval query &gt;

    The enemy troops were arrayed Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submis ...

  6. HDU 1166 The enemy troops were arrayed Line tree single point update summation

    Topic link Chinese questions , Introduction to line tree , Single point update summation , Just build a tree . #include <iostream> #include <cstdio> #include <cmat ...

  7. 【 original 】hdu 1166 The enemy troops were arrayed ( Line segment tree → Single point update , Interval query )

    The third day of learning segment trees ... I really didn't learn anything good , Another water problem , Pure template , Personally, I think my line segment tree template is good ( After all, my first day was like learning nothing ... Looking for templates all day , Compared several , I finally found my favorite type ), Chinese title ...

  8. hdu 1166 The enemy troops were arrayed Line segment tree Click Update

    // hdu 1166 The enemy troops were arrayed Line segment tree Click Update // // This problem naked line segment tree point update , Just write it // // I've always wanted to go into the pit of the segment tree , I didn't jump in , It's like jumping in today , // Simple as it is ...

  9. HDU 1754 Line segment tree Single point and new HDU 1166 The enemy troops were arrayed Line segment tree Sum of intervals

    I Hate It Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total ...

  10. hdu 1166 The enemy troops were arrayed Segment tree interval modification 、 Inquire about 、 Single point modification Board question

    Topic link : The enemy troops were arrayed subject : C The enemy of our country A China is conducting military exercises during this period , therefore C The head of the country Derek And his men Tidy I'm busy again .A Our country is in a straight line along the coastline N An engineering camp ,Derek and Tidy My task is to monitor ...

Random recommendation

  1. React state Use

    be relative to angular.js Two-way data binding ,React have access to State To achieve . React in , Just update the state, Then according to the new state Re render the user interface ( Don't operate DOM). this ...

  2. Struts2 Redirection and request forwarding configuration in

    struts2 By default, jump to dispatcher Request forwarding Only to jsp forward , Jump action newspaper 404 Redirect Set to redirect , It can be jsp It can also be action <!-- Under the same bag act ...

  3. Sqlserver Substitution function Replace

    Sqlserver in Replace function : Realize the batch replacement of a string in the field . Be careful : It is strongly recommended to back up the database before replacement to avoid catastrophic consequences . update article set [Content]=replace([ ...

  4. MVC in Razor Display of unlimited categories

    stay MVC Of Razor View shows the way of stepless classification , I read a lot of information on the Internet , Most of them are very tall . Maybe my level is limited , I really can't use it . Then I'll do it in the simplest way . Model: public class NewsCa ...

  5. HDU 3853-loop( probability dp introduction )

    The question : r*c A square , from (1,1) Start casting magic in each square ( Consume energy 2) To know , It may be in place after casting magic . It may reach the adjacent lower grid or the right grid , Give the probabilities of the three To reach (R,C) lattice , The expectation of energy consumption . analysis ...

  6. python error 、 Commissioning and testing

    While the program is running , There are always all kinds of mistakes . Some mistakes are caused by programming problems , For example, we should have output the integer result and output the string , This kind of mistake is usually called bug,bug It must be repaired . Some errors are caused by user input , Let's use ...

  7. front end -- About clients javascript

    In the browser Javascript client javascript It's running in the browser javascript, Modern browsers have made great progress , Although it's an application , But you can think of it as a simple operating system , Because like ...

  8. day05 list type

    Basic use 1 purpose : Record multiple values , For example, people's hobbies # ====================================== Basic use ================================ ...

  9. LeetCode147:Insertion Sort List

    subject : Sort a linked list using insertion sort. Their thinking : According to the title , Insert sort directly Implementation code : #include <iostream> us ...

  10. ANR android

    1.android ANR Causes and solutions 2.Android ANR Exception and solution 3.Android ANR Analyze the solution 4.[ original ]Android system stability - ANR( One ) 5.[ original ] ...