怎么办二进制索引树或树状数组一系列更新？ [英] How to do a range update in Binary Indexed Tree or Fenwick Tree?
问题描述
我试图解决<一个href="http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2397"相对=nofollow>这个的问题UVA与二进制索引树：
I am trying to solve this problem in UVA with Binary Indexed Tree:
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 at his own will. Of course, handy spells
were used. The process of changing team was known as mutating.
There were N pirates and all of the pirates have a unique id from 0 to N-1.
The great magician could mutate a bunch of pirates with consecutive id’s to
another one.
Suppose there were 100 pirates in the pirate land and all of them were
Barbary pirates, then the magician could cast a spell to change pirates with
id’s from 10 to 33 to Buccaneer pirates. Then the whole pirate land would
have 24 Buccaneer and 76 Barbary pirates.
The magician was very fast casting the spell. Once, God started to dislike this.
God had favor for the Buccaneer pirates and God asked the magician, "Tell me,
how many of the pirates of index from 2 to 30 are Buccaneer pirates?". Now the
magician was puzzled as he was only efficient in casting spells, not in counting J
Being clever enough, the magician captured a clever man from the Earth Land.
And unfortunately it’s you! Now you have to answer the God’s questions.
Input
The first line of input will contain number of test cases T.
For each test case:
The first part of the description will be of the pirate land.
There could be up to N (1<=N<=1024000) pirates. Each pirate is either
assigned to Buccaneer or Barbary Pirate. Buccaneer pirates are described
by ‘1’ (ONE) and Barbary pirates are described by ‘0’ (ZERO). You have to
build a string of the pirates’ description. Each case starts with an integer
M (M<=100), where M pair lines follow. In each pair of lines (we call it a set),
first has an integer T (T <= 200) and next one has a nonempty string Pirates
(consisting of 0 and 1, 0 for Barbary, 1 for Buccaneer, has maximum length of 50).
For each pair concatenate the string Pirates, T times. Concatenate all the
resulting M sets of strings to build the pirate description. The final
concatenated string describes the pirates from index 0 to end (N-1 for N pirates).
Now the next part of the input will contain queries.
First line of next part has an integer Q describing number of queries.
Each subsequence Q (1<=Q<=1000) lines describe each query. Each query has a
string F or E or I or S and two integers, a and b denoting indexes.
The meaning of the query string are follows:
F a b, means, mutate the pirates from index a to b to Buccaneer Pirates.
E a b, means, mutate the pirates from index a to b to Barbary Pirates.
I a b, means, mutate the pirates from index a to b to inverse pirates.
S a b, means, "God’s query" God is asking a question:
"Tell me, how many Buccaneer pirates are there from index a to b?"
(a <= b, 0 <= a < n, 0 <= b < n, index range are inclusive)
Output
For each test print the case number as the sample output suggests.
Then for each of "God’s query", output the query number, colon (:) and
a space and the answer to the query as the sample suggest.
╔══════════════╦═════════════════════════╗
║ Sample Input ║ Output for Sample Input ║
╠══════════════╬═════════════════════════╣
║ 2 ║ Case 1: ║
║ 2 ║ Q1: 5 ║
║ 5 ║ Q2: 1 ║
║ 10 ║ Case 2: ║
║ 2 ║ Q1: 0 ║
║ 1000 ║ ║
║ 5 ║ ║
║ F 0 17 ║ ║
║ I 0 5 ║ ║
║ S 1 10 ║ ║
║ E 4 9 ║ ║
║ S 2 10 ║ ║
║ 3 ║ ║
║ 3 ║ ║
║ 1 ║ ║
║ 4 ║ ║
║ 0 ║ ║
║ 2 ║ ║
║ 0 ║ ║
║ 2 ║ ║
║ I 0 2 ║ ║
║ S 0 8 ║ ║
╚══════════════╩═════════════════════════╝
Explanation:
Case1:
The pirate land is as follows (N = 18)
101010101010001000
Before God’s first query it was as follows
000000111111111111
Case 2:
The pirate land is as follows (N=9)
111000000
这是关于增加或减少值的范围为1或0，和查询是像往常一样在树状数组。
我知道如何更新在树中的特定位置。照片
当更新一个范围我只用一个循环的每个元件在该范围内，以更新为1或0，但它的花费过多时间。
It's about incrementing or decrementing a range of values to 1 or 0, and query is as usual in fenwick tree.
I know How to update at a specific position in a tree.
When updating a range I just used a loop for every element in that range to update to that 1 or 0. But Its taking too much time.
实际上它是1的阵列'和0与没有别的，并更新过程仅包括更新的范围内[A，B]至1,0或反相。 这是我的code：
Actually it's an array of 1' and 0's with nothing else, and the update procedure only includes updating a range [a,b] to 1,0 or inverting. Here's my code:
#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
typedef vector<int> vi;
class bit{
public:
bit(int n,string strt):s(strt){ ftBuc.assign(n+2,0); }
void adjust(int k,int v){
if(v=='1'&&s[k] == '1')
return;
else if(v=='0' && s[k] == '0')
return;
else if(v=='1'&&s[k] == '0')
{ s[k] = '1'; for(;k<(int)ftBuc.size();k += leastSig1(k)) ftBuc[k]+=1; }
else if(v=='0' && s[k] == '1' )
{ s[k] = '0'; for(;k<(int)ftBuc.size();k += leastSig1(k)) ftBuc[k]-=1; }
}
int rsq(int a,int b) { return rsq(b)-(a==1?0:rsq(a-1));}
string s;
int rsq(int b) { int sum = 0; for(; b ; b-=leastSig1(b)) sum+=ftBuc[b]; return sum;}
vi ftBuc;
int leastSig1(int i) {return i&(-i);}
};
int main()
{
int t;
cin>>t;
for(int test=1;test<=t;++test)
{
int m;
cin>>m;
string s;
while(m--)
{
int T;
cin>>T;
string temp;
cin>>temp;
while(T--)
s.append(temp);
}
int n = s.size();
bit ft(n+2,string(n+2,'0'));
for(int i = 1;i<=n;++i)
ft.adjust(i,s[i-1]);
int q;
cin>>q;
int asks = 1;
printf("Case %d:\n",test);
while(q--)
{
char c;
int i,j;
cin>>c>>i>>j;
if(c=='F')
{
for(int k=i+1;k<=j+1;++k)
ft.adjust(k,'1');
}
else if(c=='E')
{
for(int k=i+1;k<=j+1;++k)
ft.adjust(k,'0');
}
else if(c == 'I')
{
for(int k=i+1;k<=j+1;++k)
{
if(ft.s[k] == '1')
ft.adjust(k,'0');
else
ft.adjust(k,'1');
}
}
else if(c=='S')
printf("Q%d: %d\n",asks++,ft.rsq(i+1,j+1));
}
}
}
推荐答案
一个二进制索引树（又名树状数组）是重新$ P $一种有效的方式，以便psenting一个频率表，以便能够迅速地提取累积频率和采用N个频点来保存N分频值。
A binary indexed tree (aka Fenwick tree) is an efficient way of representing a frequency table in order to be able to quickly extract cumulative frequencies and uses N bins to hold N frequency values.
不过，对于这个问题我会建议段树代替。一个段树具有类似的结构，以二进制索引树除了它通常使用2N箱代替
However, for this problem I would recommend a segment tree instead. A segment tree has a similar structure to a binary indexed tree except it typically uses 2N bins instead.
如同树状数组，是有帮助的考虑在树作为负责一组索引的每个节点。这里的责任大小为8的分域树节点的说明：
As with the Fenwick tree, it is helpful to think about each node in the tree as being responsible for a set of indices. Here is an illustration of the responsibilities for nodes in a Fenwick tree of size 8:
Index Responsibilities
8 8
7 7 8
6 6 8
5 5 6 8
4 4 8
3 3 4 8
2 2 4 8
1 1 2 4 8
这意味着，例如，该分域条目A [4]将负责指数1,2,3,4和A [4]将包含总频率F [1] + F [2] + F [3] + F [4]
This means that, for example, the Fenwick entry A[4] will be responsible for indices 1,2,3,4 and A[4] will contain the total frequency F[1]+F[2]+F[3]+F[4].
在另一方面，在一个段树的责任将看起来像：
In contrast, the responsibilities in a segment tree will look like:
Index Responsibilities
8 1 3 7 15
7 1 3 7 14
6 1 3 6 13
5 1 3 6 12
4 1 2 5 11
3 1 2 5 10
2 1 2 4 9
1 1 2 4 8
懒更新
那么，为什么我们做了这个？
Lazy Update
So why have we done this?
原因是，我们现在有责任为每个细分范围内一个单独的条目，这让我们使用延迟更新。
The reason is that we now have a separate entry responsible for each subdivided range, and this lets us use lazy update.
与懒惰更新的想法是，当你想更新范围内，你只需要递归到该段树和细分，直到到达完全包含在范围内进行更新的时间间隔值。一旦你达到这样一个区间，你做两件事情：
The idea with lazy update is that when you wish to update a range of values you only need to recurse into the segment tree and subdivide until you reach an interval that is totally contained within the range to be updated. Once you reach such an interval you do two things:
- 更新值的时间间隔 在该节点
- 存储信息，以指示段下方仍需要进行更新
请注意，该递归过程中，你还需要推低了您遇到任何偷懒的操作。
Note that during the recursion you also need to push down up any lazy operations you encounter.
例如code，尝试搜索段树和懒传播。
For example code, try searching for "segment tree" and "lazy propagation".
段树木懒传播将花费O（日志（N））的值的任何范围的查询和更新。
Segment trees with lazy propagation will cost O(log(N)) for both queries and updates of any range of values.
这篇关于怎么办二进制索引树或树状数组一系列更新？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
