“吃布丁不吐皮”通过精心收集，向本站投稿了2篇数据结构树状数组（二叉索引树），以下是小编为大家准备的数据结构树状数组（二叉索引树），仅供参考，欢迎大家阅读。
篇1：数据结构树状数组（二叉索引树）
树状数组适用于动态连续和查询问题，就是给定一个区间，
查询某一段的和或者修改某一位置的值，
关于树状数组的结构请去百度百科,否则将看不懂下面内容
我们看这个题
士兵杀敌（二）
时间限制：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 一、树状数组 在解题过程中，我们有时需要维护一个数组的前缀和 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） 【问题描述】 老管家是一个聪明能干的人， 他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记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：树状数组和线段树
数据结构树状数组（二叉索引树）（整理2篇）
