树状数组中,每个结点管辖了不同的原数组元素的和。
令A[1...n]表示原数组,C[1...n]表示树状树组。
观察图,可知:
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
...
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16
这里有一个有趣的性质:
设结点编号为x,那么这个节点管辖的区间有2^k(其中k为x二进制末尾0的个数)个元素。因为这个区间最后一个元素必然为A[x],所以很明显:C[x] = A[x – 2^k + 1] + ... + A[x]。
算这个2^k有一个快捷的办法,定义如下一个函数,返回x的2^k。
int lowBit(int x) {
return x & (-x);
}
计算数组A[1...x]的和,算法如下:
step1: 令sum = 0,转第二步;
step2: 假如x <= 0,算法结束,返回sum值,否则sum = sum + C[x],转第三步;
step3: 令x = x – lowBit(x),转第二步。
函数如下:
int sum(int x) {
int s = 0;
while(x > 0) {
s += C[x];
x -= lowBit(x);
}
return s;
}
修改某个A[x]元素(将A[x]的值增加t),算法如下:
step1: 当x > n时,算法结束,否则转第二步;
step2: C[x] = C[x] + t, x = x + lowBit(x)转第一步。
函数如下:
void update(int x, int t) {
while(x < n) {
C[x] += t;
x += lowBit(x);
}
}
好了,来看POJ这道题。
题意
一个“*”的层次是这样定义的,处于该“*”的下面和左面的范围内的“*”的个数即为该“*”的层次。题目要求处于0到n-1层次的“*”数目各有几个。
分析
由于“*”的坐标已经按Y递增的顺序排列好,对于具有相同Y坐标的“*”,又按其X坐标排序,故可充分利用这一输入特点,直接运用树状数组进行求解。
代码
分享到:
相关推荐
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客poj-1002源码,没有题解,题解看博客
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
西北工业大学-c语言-POJ-题目及答案-第七季.doc
POJ-3299解题 C++源代码 Description Adapted from Wikipedia, the free encyclopedia The humidex is a measurement used by Canadian meteorologists to reflect the combined effect of heat and humidity. It...
poj-2528 Mayor's posters 测试数据及答案
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
算法-炮兵阵地(POJ-1185)(包含源程序).rar
算法-开关问题(POJ-1830)(包含源程序).rar
算法-青蛙的约会(POJ-1061)(包含源程序).rar
北大POJ2002-Squares 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
POJ - 2136. VerticalHistogram(统计字母个数)题目链接题目就是给你四行字符串,然后要你统计大写字母(只有大写字母)的个数,然后以特定
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501