标签: fenwick-tree

如何使用二进制索引树(BIT)找到一定长度的增加子序列的总数？

实际上这是Spoj Online Judge的一个问题

示例
假设我有一个数组1,2,2,10

增加的长度为3的子序列是1,2,4和1,3,4

所以,答案是2.

上下文

我有一个应用程序从表中选择加权随机条目,其中前缀总和(权重)是关键部分.简化的表定义如下所示:

CREATE TABLE entries (
    id INT NOT NULL PRIMARY KEY AUTO_INCREMENT,
    weight DECIMAL(9, 3),
    fenwick DECIMAL(9, 3)
) ENGINE=MEMORY;

其中`fenwick`存储Fenwick树表示中的值`weights`.

让每个条目的"范围"跨越其前缀和与其前缀sum +其权重之间.应用程序必须@r在0和之间生成一个随机数,SUM(weight)并查找其范围包含的条目@r,如下所示:

Fenwick树,结合MEMORY引擎和二进制搜索,应该允许我及时找到合适的条目O(lg^2(n)),而不是O(n)天真查询的时间:

SELECT a.id-1 FROM (SELECT *, (@x:=@x+weight) AS counter FROM entries 
    CROSS JOIN (SELECT @x:=0) a
    HAVING counter>@r LIMIT 1) a;

研究

由于多个查询的开销,我一直在尝试将前缀sum操作压缩成一个查询(而不是脚本语言中的几个数组访问).在这个过程中,我意识到传统的求和方法,即涉及按降序键顺序访问元素,只会求和第一个元素.我怀疑MySQL在WHERE子句中存在变量时会线性地运行表.这是查询:

SELECT
SUM(1) INTO @garbage
FROM entries 
CROSS JOIN (
    SELECT @sum:=0,
        @n:=@entryid
) …

给定n个整数的未排序数组,我知道我可以在这个方法之后找到使用BIT在O(N lg N)中的反转总数:BIT计数反转

但是,如果我必须在O(lg N)中查询反转总数的任意范围,是否可能？

AO(N lg N)预计算是可接受的.

我做了一些研究,似乎N因素是不可避免的...任何建议将不胜感激!

我有一个三维fenwick树数据结构.我需要从一些片段计算总和(x0, y0, z0),以(x, y, z)

包含 - 排除的公式是什么？例如,对于2D变体,它是

s = sum(x, y) - sum(x, y0 - 1) - sum(x0 - 1, y) + sum(x0 - 1, y0 - 1)

提前致谢

http://www.comp.nus.edu.sg/~stevenha/ft.pdf

这是2D案例:

我试图理解算法,它给出了时间O(n k log(n))中数组中长度K的增加子序列的数量.我知道如何使用O(k*n ^ 2)算法解决同样的问题.我查了一下,发现这个解决方案使用了BIT(Fenwick Tree)和DP.我也找到了一些代码,但我无法理解它.

以下是我访问过的一些有用的链接.

这里在SO
Topcoder论坛
随机网页

如果有人能帮助我理解这个算法,我真的很感激.

我试图用二进制索引树在UVA中解决这个问题:

Problem H
Ahoy, Pirates!

Input: Standard Input
Output: Standard Output


In the ancient pirate ages, the Pirate Land was divided into two teams of pirates,  
namely, the Buccaneer and the Barbary pirates. Each pirate’s team was not fixed,  
sometimes the opponent pirates attacked and he was taken away to the other pirate team.  
All on a sudden a magician appeared in the Pirate Land, where he was making transition  
of pirates from their team to other team …

任何人都可以帮我完成这项任务http://www.spoj.com/problems/INVCNT/.首先,我尝试用BIT方式思考,但我不能.任何人都可以用BIT解释这个任务的解决方案.BIT-二进制索引树c ++

这是我想要解决的问题,我使用The Fact That Prefix Sum[i] - Prefix Sum[i-1]导致频率大于零来识别不同的数字然后我正在消除频率,但即使有BIT,我也得到了一个TLE

给定n个数字序列a1,a2,...,an和许多d查询.

d查询是一对(i,j)(1≤i≤j≤n).

对于每个d查询(i,j),您必须返回子序列ai,ai + 1,...,aj中的不同元素的数量.

Input

Line 1: n (1 ? n ? 30000).
Line 2: n numbers a1, a2, ..., an (1 ? ai ? 106).
Line 3: q (1 ? q ? 200000), the number of d-queries.
In the next q lines, each line contains 2 numbers i, j 
representing a d-query (1 ? i ? j ? n).

Output

For each d-query (i, j), print the number …