“炫菠萝”通过精心收集，向本站投稿了6篇树状数组和线段树，下面小编给大家整理后的树状数组和线段树，供大家阅读参考。
- 目录
篇1：树状数组和线段树
一、树状数组
在解题过程中，我们有时需要维护一个数组的前缀和 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.
篇2：数据结构树状数组（二叉索引树）
树状数组适用于动态连续和查询问题，就是给定一个区间，
查询某一段的和或者修改某一位置的值，
关于树状数组的结构请去百度百科,否则将看不懂下面内容
我们看这个题
士兵杀敌（二）
时间限制：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 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 StarsTime Limit:1000MSMemory Limit:65536KTotal Submissions:35467Accepted:15390 Description 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 Output Sample Input 51 15 17 13 35 5 Sample Output 12110 Hint Source 题意：问在输入的点（星星）的坐标的左下方（包含左方和下方）有几个点（星星）， POJ 2352 Stars（树状数组）篇3：hdu 5147 树状数组
篇4：POJ 2352 Stars（树状数组）
，
有几个点（星星）就是第几种情况，一共有1~n种情况，输出每种情况的个数。因为题目保证y的坐标是按升序输入的，所以就不用考虑y，只需要更新x的树状数组就可以了。
#include
篇5：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
篇6：POJ 2155 Matrix（树状数组）
MatrixTime Limit:3000MSMemory Limit:65536KTotal Submissions:20138Accepted: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篇）
