下面是小编帮大家整理的hdu 5147 树状数组，本文共9篇，欢迎阅读，希望大家能够喜欢。
篇1：hdu 5147 树状数组
Problem Description Long long ago, there is a sequence A with length n. All numbers in this sequence is no smaller than 1 and no bigger than n, and all numbers are different in this sequence.
Please calculate how many quad (a,b,c,d) satisfy:
1.
2.
3.
Input The first line contains a single integer T, indicating the number of test cases.
Each test case begins with a line contains an integer n.
The next line follows n integers
[Technical Specification]
1 <= T <= 100
1 <= n <= 50000
1 <=
Output For each case output one line contains a integer,the number of quad.
Sample Input
151 3 2 4 5
Sample Output
4
/**hdu5147 树状数组解题思路： 要统计四元组的数量我们可以通过枚举c，然后统计区间[1,c-1]有多少二元组(a,b)满足a#include
篇2：树状数组和线段树
一、树状数组
在解题过程中，我们有时需要维护一个数组的前缀和 S[i]=A[1]+A[2]+...+A[i] ，但是不难发现，如果我们修改了任意一个 A[i],S[i] 、S[i+1]...S[n] 都会发生变化。可以说，每次修改 A[i] 后，调整前缀和 S[] 在最坏情况下会需要 O(n) 的时间。当 n 非常大时，程序会运行得非常缓慢。因此，这里我们引入“树状数组”，它的修改与求和都是 O(logn) 的，效率非常高。
实现：
对于正整数x，定义lowbit（x）为x的二进制表达式中最右边的1所对应的值。
Lowbit(x)=x and -x对于节点i，如果它是左子节点，其父节点为i+lowbit(i)；
构造一个辅助数组C，其中Ci=Ai-lowbit(i)+1+Ai-lowbit(i)+2+…+Ai即C的每个元素都是A数组中的一段连续和。具体是每个灰色节点i都属于一个以它自身结尾的水平长条，这个长条中的数之和就是Ci。如C12=A9+A10+A11+A12=C10+A11+A12
如何更新C数组中的元素：如果修改了一个Ai，需要更新C数组中的哪些元素呢？从Ci开始往右走，边走边“往上爬”（不一定沿着树中的边爬），沿途修改所有结点对应的Ci即可。预处理时先把C数组清空，然后执行n次add操作。总时间为O（nlogn）
如何计算前缀和Si：顺着结点i往左走，边走边“往上爬”（不一定沿着树中的边爬），把沿途经过的Ci累加起来就可以了。对于query（L,R）=SR-SL-1。
代码：
var
b,c,f:array [0..100000] of longint;
ff,a:Array [0..100000] of boolean;
i,j,m,n,x,y,ans,l,r,tmp:longint;
s:string;
function dfs(x:longint):longint;
begin
if x<=1 then
exit;
c[f[x]]:=c[f[x]]+c[x];
dfs(f[x]);
end;
procedure dfs1(x:longint);
begin
dec(c[x]);
if x<=1 then
exit;
dfs1(f[x]);
end;
procedure dfs2(x:longint);
begin
inc(c[x]);
if x<=1 then
exit;
dfs2(f[x]);
end;
begin
readln(n);
fillchar(ff,sizeof(ff),true);
for i:=1 to n-1 do
begin
readln(x,y);
f[y]:=x;
inc(b[x]);
end;
for i:=1 to n do
c[i]:=1;
for i:=1 to n do
begin
if b[i]=0 then
dfs(i);
end;
readln(m);
for i:=1 to m do
begin
x:=0;
readln(s);
if s[1]='Q' then
begin
for j:=3 to length(s) do
x:=x*10+ord(s[j])-ord('0');
writeln(c[x]);
end;
if s[1]='C' then
begin
for j:=3 to length(s) do
x:=x*10+ord(s[j])-ord('0');
if ff[x] then
dfs1(x) else
dfs2(x);
ff[x]:=not ff[x];
end;
end;
End.
二、线段树
1,.线段树的结构:
区间：用一对数a和b表示一个前闭后开的区间[a,b)。（可以自己修改）结点T(a,b)：表示该结点维护了原数列中区间[a,b)的信息，其中a和b为整数且a1，那么T(a,(a+b)/2)为T(a,b)的左孩子结点，T((a+b)/2,b)为T(a,b)的右孩子
叶结点：如果对于结点T(a,b)，有b-a=1，那么该结点就是叶结点线段树结构是递归定义的。
2.线段树的性质:
结点数：假设该线段树处理的数列长度为n，即根结点的区间为[1,n+1)，那么总结点个数不超过2*n个。深度：线段树可以近似看做一棵满二叉树，所以深度不超过log（2*n）线段分解数量级：线段树把区间上的任意一条长度为L的线段都分成了不超过2logL条线段，这使得大多数查询能够在O（logn）的时间内解决。
线段树的存储：
1、链表存储
2、数组模拟链表
3、堆结构存储
应用：
忠诚（loyal）
【问题描述】
老管家是一个聪明能干的人，
他为财主工作了整整，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。
在询问过程中账本的内容可能会被修改
【输入格式】
输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。
接下来每行为3个数字，第一个p为数字1或数字2，第二个数为x，第三个数为y
当p=1 则查询x,y区间
当p=2 则改变第x个数为y
【输出格式】
输出文件中为每个问题的答案。具体查看样例。
【输入样例】
10 3
1 2 3 4 5 6 7 8 9 10
1 2 7
2 2 0
1 1 10
【输出样例】
2 0
代码：
type
point=^node;
node=record
left,right:longint;
lp,rp:point;
sum:longint;
end;
var
p:array [1..100000] of node;
i,j,m,n,x,y,k:longint;
a:array [1..100000] of longint;
root:point;
procedure creat(p:point;l,r:longint);
begin
p^.left:=l; p^.right:=r; p^.sum:=maxlongint;
if l+1=r then
begin
p^.lp:=nil;
p^.rp:=nil;
end
else
begin
new(p^.lp); creat(p^.lp,l,(l+r) div 2);
new(p^.rp); creat(p^.rp,(l+r) div 2,r);
end;
end;
function min(x,y:longint):longint;
begin
if x
exit(x);
exit(y);
end;
procedure update(p:point;x,delta:longint);
begin
if p^.left+1=p^.right then
begin
p^.sum:=delta;
end
else
begin
if x<(p^.left+p^.right) div 2 then
update(p^.lp,x,delta);
if x>=(p^.left+p^.right) div 2 then
update(p^.rp,x,delta);
p^.sum:=min(p^.lp^.sum,p^.rp^.sum);
end;
end;
function query(p:point;l,r:longint):longint;
var
ans:longint;
begin
if (l<=p^.left) and (p^.right<=r) then
exit(p^.sum);
ans:=maxlongint;
if l<(p^.left+p^.right) div 2 then
ans:=min(ans,query(p^.lp,l,r));
if r>(p^.left+p^.right) div 2 then
ans:=min(ans,query(p^.rp,l,r));
exit(ans);
end;
begin
readln(n,m);
for i:=1 to n do
read(a[i]);
new(root);
creat(root,1,n+1);
for i:=1 to n do
update(root,i,a[i]);
for i:=1 to m do
begin
readln(k,x,y);
if k=2 then
update(root,x,y);
if k=1 then
write(query(root,x,y+1),' ');
end;
writeln;
End.
篇3：POJ 2352 Stars（树状数组）
StarsTime Limit:1000MSMemory Limit:65536KTotal Submissions:35467Accepted:15390
Description
Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.
You are to write a program that will count the amounts of the stars of each level on a given map.
Input
The first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=3). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.Output
The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.Sample Input
51 15 17 13 35 5
Sample Output
12110
Hint
This problem has huge input data,use scanf instead of cin to read data to avoid time limit exceed.Source
Ural Collegiate Programming Contest题意：问在输入的点（星星）的坐标的左下方（包含左方和下方）有几个点（星星），
POJ 2352 Stars（树状数组）
，
有几个点（星星）就是第几种情况，一共有1~n种情况，输出每种情况的个数。因为题目保证y的坐标是按升序输入的，所以就不用考虑y，只需要更新x的树状数组就可以了。
#include
篇4：Stars （poj 2352 树状数组）
Language:StarsTime Limit:1000MSMemory Limit:65536KTotal Submissions:35169Accepted:15259
Description
Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.
You are to write a program that will count the amounts of the stars of each level on a given map.
Input
The first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.Output
The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.Sample Input
51 15 17 13 35 5
Sample Output
12110
Hint
This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.Source
Ural Collegiate Programming Contest 1999题意：有n个星星的坐标，如果某个星星坐标为(x, y), 它的左下位置为：(x0,y0)，x0<=x 且y0<=y，
Stars （poj 2352 树状数组）
，
如果左下位置有a个星星，就表示这个星星属于level x
按照y递增，如果y相同则x递增的顺序给出n个星星，求出所有level水平的数量。
思路：最典型的树状数组，第一次做。。
代码：
#include
篇5：POJ 2155 Matrix（树状数组）
MatrixTime Limit:3000MSMemory Limit:65536KTotal Submissions:8Accepted:7522
Description
Given an N*N matrix A, whose elements are either 0 or 1. A[i, j] means the number in the i-th row and j-th column. Initially we have A[i, j] = 0 (1 <= i, j <= N).We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using “not” operation (if it is a '0' then change it into '1' otherwise change it into '0'). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.
1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2).
2. Q x y (1 <= x, y <= n) querys A[x, y].
Input
The first line of the input is an integer X (X <= 10) representing the number of test cases. The following X blocks each represents a test case.The first line of each block contains two numbers N and T (2 <= N <= 1000, 1 <= T <= 50000) representing the size of the matrix and the number of the instructions. The following T lines each represents an instruction having the format “Q x y” or “C x1 y1 x2 y2”, which has been described above.
Output
For each querying output one line, which has an integer representing A[x, y].There is a blank line between every two continuous test cases.
Sample Input
12 10C 2 1 2 2Q 2 2C 2 1 2 1Q 1 1C 1 1 2 1C 1 2 1 2C 1 1 2 2Q 1 1C 1 1 2 1Q 2 1
Sample Output
1001
Source
POJ Monthly,Lou Tiancheng题意：poj1566的二维版，有一个矩阵，矩阵中的每个元素只能有0,1，表示，给定一个矩形的左上角和右下角，在这个矩形中的元素进行取反，
POJ 2155 Matrix（树状数组）
，
当输入的字符为Q是，输出地址为x行y列的那个元素是0还是1.
#include
篇6：POJ 2155 Matrix 二维树状数组
二维树状数组，是一维的演变版，没什么太大改动
要注意的是，这里数组必须重新定义，不能是默认定义a[i][j]表示a[i][j]的值，否则二维树状数组只能做到单点修改，区间查询，但此题需要区间修改，
所以不妨换定义，定义a[i][j]表示 a[ i1 ] [ j1 ] ( i =< i1 <= n && j <= j1 <= n )所有值之和，那么修改时，只需将 a [ x1 ][ y1 ] += 1, a [ x1 ][ y2 + 1 ] -= 1; a [ x2 ][ y1 + 1] -= 1; a[ x2 + 1 ][ y2 + 1 ] +=1; 这个操作不是简单的 +1 -1，而是在二维树状数组上进行。
如此，查找时，只需查找 a[x][y] 即可，这也不是简单的查找a[x][y]，而是在二维树状数组上进行。具体看代码。
二维线段树个人还不会，一会学学博主的。
My code (Java)
import java.util.*;public class Main { public static void main(String[] agrs){ Scanner input = new Scanner(System.in); int T = input.nextInt(); int n, m; BIT bit; for(int kase = 1; kase <= T; kase++){if(kase >1) System.out.println();n = input.nextInt(); m = input.nextInt();bit = new BIT(n);for(int i = 1; i <= m; i++){ String s = input.next(); if(s.charAt(0) == 'C'){ int x1, y1, x2, y2; x1 = input.nextInt(); y1 = input.nextInt(); x2 = input.nextInt(); y2 = input.nextInt(); bit.update(x1 , y1, +1); bit.update(x1, y2 + 1, -1); bit.update(x2 + 1, y1, -1); bit.update(x2 + 1, y2 + 1, +1); } else{ int x, y; x = input.nextInt(); y = input.nextInt(); int ans = bit.query(x, y); ans = (ans % 2 + 2) % 2; System.out.println(ans); }} } input.close(); }}class BIT{ int[][] a; int n; public BIT(int n){ this.n = n; a = new int[n + 10][n + 10]; } public void update(int x,int y,int val){ for(int i = x; i <= n; i += i&-i){for(int j = y; j <= n; j += j&-j){ a[i][j] += val; a[i][j] = (a[i][j] % 2 + 2) % 2;} } } public int query(int x,int y){ int ans = 0; for(int i = x; i >0; i -= i&-i){for(int j = y; j >0; j -= j&-j){ ans = (ans + a[i][j]) % 2;} } return ans; }}
篇7：NYOJ117&& 树状数组求逆序数
树状数组可以用来求逆序数， 当然一般用归并求，如果数据不是很大， 可以一个个插入到树状数组中， 每插入一个数， 统计比他小的数的个数，对应的逆序为 i- getsum( da
ta[i] ),其中 i 为当前已经插入的数的个数， getsum( da
ta[i] ）为比 da
ta[i] 小的数的个数i- sum( da
ta[i] ) 即比 da
ta[i] 大的个数， 即逆序的个数但如果数据比较大，就必须采用离散化方法。一关键字的离散化方法：所谓离散化也就是建立一个一对一的映射。 因为求逆序时只须要求数据的相应
大小关系不变。如： 10 30 20 40 50 与 1 3 2 4 5 的逆序数是相同的定义一个结构体 struct Node{ int data; // 对应数据 int pos; // 数据的输入顺序 };
先对 da
ta 升序排序， 排序后，pos 值对应于排序前 da
ta 在数组中的位置。再定义一个数组 p[N]， 这个数组为原数组的映射。以下语句将按大小关系把原数组与 1到 N 建立一一映射。
题目链接：click here
预备函数
定义一个Lowbit函数，返回参数转为二进制后,最后一个1的位置所代表的数值.
例如,Lowbit(34)的返回值将是2；而Lowbit(12)返回4；Lowbit(8)返回8。
将34转为二进制,为0010 0010,这里的“最后一个1”指的是从2^0位往前数,见到的第一个1,也就是2^1位上的1.
程序上，((Not I)+1) And I表明了最后一位1的值,
仍然以34为例,Not 0010 0010的结果是 1101 1101(221),加一后为 1101 1110(222), 把 0010 0010与1101 1110作AND,得0000 0010(2).
Lowbit的一个简便求法:（C++）
int lowbit(int x){ return x&(-x);}
新建
定义一个数组 BIT，用以维护A的前缀和，则:
具体能用以下方式实现：（C++）
void build{ for (int i=1;i<=MAX_N;i++) { BIT[i]=A[i]; for (int j=i-1; j>i-lowbit(i);j-=lowbit(j))BIT[i]+=BIT[j]; }}
修改
假设现在要将A[I]的值增加delta,
那么,需要将BTI[I]覆盖的区间包含A[I]的值都加上K.
这个过程可以写成递归,或者普通的循环.
需要计算的次数与数据规模N的二进制位数有关,即这部分的时间复杂度是O(LogN)
修改函数的C++写法
void edit(int i, int delta){ for (int j = i; j<= MAX_N; j += lowbit(j)) BIT[j] += delta;}
求和
首先,将ans初始化为0，将i计为k.将ans的值加上BIT[P]将i的值减去lowbit(i)重复步骤2～3，直到i的值变为0
求和函数的C/C++写法
int sum (int k){ int ans = 0; for (int i = k; i >0; i -= lowbit(i)) ans += BIT[i]; return ans;}
复杂度
初始化复杂度最优为O(N)
单次询问复杂度O(LOG(N))其中N为数组大小
单次修改复杂度O(LONG(N))其中N为数组大小
空间复杂度O(N);
代码：#include 归并排序合并算法 #include 树状数组适用于动态连续和查询问题，就是给定一个区间， 查询某一段的和或者修改某一位置的值， 关于树状数组的结构请去百度百科,否则将看不懂下面内容 我们看这个题 士兵杀敌（二） 时间限制：1000 ms | 内存限制：65535 KB 难度：5 描述 南将军手下有N个士兵，分别编号1到N，这些士兵的杀敌数都是已知的。 小工是南将军手下的军师，南将军经常想知道第m号到第n号士兵的总杀敌数，请你帮助小工来回答南将军吧。 南将军的某次询问之后士兵i可能又杀敌q人，之后南将军再询问的时候，需要考虑到新增的杀敌数。 输入 只有一组测试数据 第一行是两个整数N,M，其中N表示士兵的个数(1 随后的一行是N个整数，ai表示第i号士兵杀敌数目。(0<=ai<=100) 随后的M行每行是一条指令，这条指令包含了一个字符串和两个整数，首先是一个字符串，如果是字符串QUERY则表示南将军进行了查询操作，后面的两个整数m,n，表示查询的起始与终止士兵编号；如果是字符串ADD则后面跟的两个整数I,A(1<=I<=N,1<=A<=100),表示第I个士兵新增杀敌数为A. 输出 对于每次查询，输出一个整数R表示第m号士兵到第n号士兵的总杀敌数，每组输出占一行 样例输入 5 6 1 2 3 4 5 QUERY 1 3 ADD 1 2 QUERY 1 3 ADD 2 3 QUERY 1 2 QUERY 1 5 样例输出 6 8 8 20 这就是典型的动态区间连续和查询问题。 树状数组需要三个函数 int lowBit(int x){ return x&(-x); //返回的值是2的k次幂，k为x二进制下从低位到高位0的个数}int sum(int n){ int res = 0; while (n >0){ res += c[n]; n -= lowBit(n); } return res;}void change(int i, int x, int n){ if (i >n) return; c[i] += x; change(i + lowBit(i), x, n);} 对于lowBit我解释一下，为什么是 x & -x，计算机里的整数采用补码表示 因此-x其实是按位取反，然后在末尾加1的结果，举个例子 32388 = 1001010110010000 -32388 = 0110101001110000 所以lowBit返回的值是x在二进制下从低位到高位最右面的1所对应的值 完整程序在下面 #include Mobile phonesTime Limit:5000MSMemory Limit:65536KTotal Submissions:15968Accepted:7373 Description Write a program, which receives these reports and answers queries about the current total number of active mobile phones in any rectangle-shaped area. Input The values will always be in range, so there is no need to check them. In particular, if A is negative, it can be assumed that it will not reduce the square value below zero. The indexing starts at 0, e.g. for a table of size 4 * 4, we have 0 <= X <= 3 and 0 <= Y <= 3. Table size: 1 * 1 <= S * S <= 1024 * 1024 Cell value V at any time: 0 <= V <= 32767 Update amount: -32768 <= A <= 32767 No of instructions in input: 3 <= U <= 60002 Maximum number of phones in the whole table: M= 2^30 Output Sample Input 0 41 1 2 32 0 0 2 2 1 1 1 21 1 2 -12 1 1 2 3 3 Sample Output 34 Source 题意：第一行输入两个数据id,n，分别代表编号和矩阵的大小，后面的数据每一行第一个数据代表编号，1代表会输入3个数想，有，z代表将矩阵中位置行x，列为y的元素加z（初始化矩阵中所有的元素都为0），2代表会输入4个数xx,yy,x,y， POJ 1195 Mobile phones（二维树状数组） ， 代表输出左上角坐标为x,y，右下角坐标为xx,yy的矩阵中所有元素的和 #include ★后缀数组 文档为doc格式篇8：数据结构树状数组（二叉索引树）
篇9：POJ 1195 Mobile phones（二维树状数组）
