Title address :

pid=1166">HDU 1166

It's said that Hu Hao's line segment tree is very famous .

So I visited his blog . Here are the details . So he wrote the code in the style of Hu Hao and Daniel .

As for the principle . What Mr. Peng Peng has said is only clear .

I'll explain the principle in the following code . To commemorate the first hair line segment tree .

Here's the code + gaze .

#include <iostream>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <stack>
using namespace std;
#define lson l, mid, rt<<1// Define child nodes directly , Because it's used every time , So it's very convenient to define one directly
#define rson mid+1, r, rt<<1 | 1
const int MAXN=51000;
int sum[MAXN<<2];
void PushUP(int rt)// Update the value of the parent node up
{
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l, int r, int rt)// Build a binary tree
{
if(l==r)// We've reached the bottom leaf node , That is, a single point , Enter the value directly
{
scanf("%d",&sum[rt]);
return ;
}
int mid=(l+r)>>1;
build(lson);// Continue to build a binary tree to the left child node
build(rson);// Continue to build a binary tree on the right child node
PushUP(rt);// Update the value of the parent node after all the nodes are established
}
void update(int p, int x, int l, int r, int rt)// A single change
{
if(l==r)// It means that we have reached the bottom leaf node , It's already a single point , The value can be changed directly
{
sum[rt]+=x;
return ;
}
int mid=(l+r)>>1;
if(p<=mid) update(p,x,lson);// Suppose the value to be changed is on the left side of this interval , Go to the left child node and continue to search
else update(p,x,rson);// Suppose the value to be changed is on the right side of this interval , Go to the right child node and continue to search
PushUP(rt);// After the change . Still update the value of the parent node up
}
int query(int ll, int rr, int l, int r, int rt)// Interval query
{
if(ll<=l&&rr>=r)// Suppose that the interval to be queried completely covers the child node . Directly return the value of the child node
return sum[rt];
int mid=(l+r)>>1;
int ans=0;
if(ll<=mid) ans+=query(ll,rr,lson);// Suppose another section to be queried on the left side of the child node . Go to the left subtree and continue to query
if(rr>mid) ans+=query(ll,rr,rson);// Suppose another section to be queried on the right side of the child node , Go to the right subtree and continue to query
return ans;
}
int main()
{
int t, n, i, a, b, ans, num=0;
char s[20];
scanf("%d",&t);
while(t--)
{
num++;
printf("Case %d:\n",num);
memset(sum,0,sizeof(sum));
scanf("%d",&n);
build(1,n,1);// establish
/*for(i=1;i<=25;i++)
{
printf("%d %d\n",i,sum[i]);
}*/
getchar();
while(scanf("%s",s))
{
if(s[0]=='E') break;
if(!strcmp(s,"Add"))
{
scanf("%d%d",&a,&b);
update(a,b,1,n,1);// changes
}
else if(!strcmp(s,"Sub"))
{
scanf("%d%d",&a,&b);
update(a,-b,1,n,1); // changes
}
else
{
scanf("%d%d",&a,&b);
ans=query(a,b,1,n,1);// Inquire about
printf("%d\n",ans);
}
}
}
return 0;
}

HDU 1166 The enemy troops were arrayed ( Line segment tree ) 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 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 ...

  3. 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 ...

  4. 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< ...

  5. 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 ...

  6. 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 ...

  7. hdu 1166 The enemy troops were arrayed ( Line segment tree 、 Single point update )

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

  8. 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 ...

  9. HDU 1166 The enemy troops were arrayed Line segment tree

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

  10. HDU 1166 - The enemy troops were arrayed - [ Line segment tree ][ Tree array ]

    Topic link :http://acm.hdu.edu.cn/showproblem.php?pid=1166 Time Limit: 2000/1000 MS (Java/Others) Memory Li ...

Random recommendation

  1. Agile transformation process - Sprint3 Review meeting

    I : Tech Leader The team : Team members are distributed in two cities , My city includes I have 4 Members , Another city includes SM Yes 7 Members . And because of our BA quit , I'll take the place of IT Of PO Position .PM In the same city with me , But he didn't ...

  2. ubuntu16.04 Lower installation jdk and android studio

    1 In the first JDK Download the corresponding Linux Of JDK edition . After entering the website , First choose Accept License Agreement Then you can download . My Linux System is ubuntukylin 16.04  64 ...

  3. read Effective Java Note it one:static Factory methods instead of Constructors ( Static factory and constructor )

    There are many ways to get instances of a class , In many ways , They have their own advantages and disadvantages , Each has its own characteristics . here , Just introduce 2 Medium method 1. Use the construction method public class Person { private String sex; /** ...

  4. Cisco IOS debug command reference Command A through D

    debug aaa accounting through debug auto-config debug aaa accounting : to display information on acco ...

  5. About the Reshaper Add code template code snippet in

    http://www.cnblogs.com/tristinjet/archive/2009/08/19/1550203.html Go to tools-> Template edit settings in the template

  6. Selenium automated testing (java Language )

    Selenium Introduce Selenium 1.0 contain core. IDE. RC. grid Four parts ,  selenium 2.0 It was when two big bulls met and communicated with each other that they decided to structure the object-oriented system ( OOPP) And convenient for ...

  7. office2013 Crack tools

    Finally, we found a cracking tool , Every time open word The activation dialog box pops up for all documents , I'm really upset , I'll give you the cracking tools first !!!! Tool name : HEU-KMS-ActivatorV1.1 The green version link : office2013 and ...

  8. HTTP protocol Turn from the little tank

    --  This article is a reprint of small tank ; The purpose of copying articles directly is that the original article address is often reset , Can't find the original article . Little tank blog Garden Home page :https://home.cnblogs.com/u/TankXiao/ Today, web programmatic ...

  9. [ turn ] use virtualBox install centos Set up the network and communication

    In this paper, from :https://blog.csdn.net/hsl_1990_08_15/article/details/51644451 Specific installation and in VM Ware It's the same way to install in After installation, we set up ...

  10. Arria10_emif

    DDR3  By row (Rank), body (Bank), That's ok (Row), Column (Column) It's a four-dimensional structure . Arria10 It's the first support ddr4 Of altera Arria10 New structure compared with the old device (1)  More hard ( ...