この CodeChef の問題を解決しようとしています:
テーブルには N 個のコインがあり、0 から N - 1 までの番号が付けられています。
次の 2 種類の操作を実行する必要があります。
A から B までの番号のコインをすべて裏返します。これは、コマンド「0 A B」で表されます。
A から B までの番号のコインのうち、表が何枚あるか答えてください。これは、コマンド「1 A B」で表されます。
入力: 最初の行には 2 つの整数 N と Q が含まれます。次の Q 行はそれぞれ、前述のように "0 A B" または "1 A B" のいずれかの形式です。
出力: 対応するクエリに必要な回答を含む「1 A B」形式のクエリごとに 1 行を出力します。
私が使用したのはセグメントツリーです。そのため、ユーザーがタイプ 1 AB のクエリを入力するたびに、出力はその間隔 [A,B] での合計になります。ただし、Time Limit Exceeded エラーが発生します。エラーは更新ステップ 0 A B が原因だと思います。配列内の要素を更新した後、ツリーを再構築します。コードを以下に示します。誰かがより迅速に更新する方法を教えてくれますか?
ところで-サンプル入力に必要な出力を取得しています。
public class SegmentTree
{
private int[] tree;
private int maxsize;
private int height;
private static int elems[];
private final int STARTINDEX = 0;
private final int ENDINDEX;
private final int ROOT = 0;
public SegmentTree(int size)
{
height = (int)(Math.ceil(Math.log(size) / Math.log(2)));
maxsize = 2 * (int) Math.pow(2, height) - 1;
tree = new int[maxsize];
ENDINDEX = size - 1;
}
private int leftchild(int pos)
{
return 2 * pos + 1;
}
private int rightchild(int pos)
{
return 2 * pos + 2;
}
private int mid(int start, int end)
{
return (start + (end - start) / 2);
}
private int getSumUtil(int startIndex, int endIndex, int queryStart, int queryEnd, int current)
{
if (queryStart <= startIndex && queryEnd >= endIndex)
{
return tree[current];
}
if (endIndex < queryStart || startIndex > queryEnd)
{
return 0;
}
int mid = mid(startIndex, endIndex);
return getSumUtil(startIndex, mid, queryStart, queryEnd, leftchild(current))
+ getSumUtil( mid + 1, endIndex, queryStart, queryEnd, rightchild(current));
}
public int getSum(int queryStart, int queryEnd)
{
if(queryStart < 0 || queryEnd > tree.length)
{
return -1;
}
return getSumUtil(STARTINDEX, ENDINDEX, queryStart, queryEnd, ROOT);
}
private int constructSegmentTreeUtil(int startIndex, int endIndex, int current)
{
if (startIndex == endIndex)
{
tree[current] = elems[startIndex];
return tree[current];
}
int mid = mid(startIndex, endIndex);
tree[current] = constructSegmentTreeUtil(startIndex, mid, leftchild(current))
+ constructSegmentTreeUtil(mid + 1, endIndex, rightchild(current));
return tree[current];
}
public void constructSegmentTree()
{
constructSegmentTreeUtil(STARTINDEX, ENDINDEX, ROOT);
}
public static void main(String[]args) throws IOException
{
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer str = new StringTokenizer(buf.readLine());
int n = Integer.parseInt(str.nextToken());
int q = Integer.parseInt(str.nextToken());
SegmentTree segmentTree = new SegmentTree(n);
int elements[] = new int[n];
for(int i = 0; i < n; i++) {
elements[i] = 0;
}
elems = elements;
segmentTree.constructSegmentTree();
while (q-- > 0) {
str = new StringTokenizer(buf.readLine());
int x = Integer.parseInt(str.nextToken());
int a = Integer.parseInt(str.nextToken());
int b = Integer.parseInt(str.nextToken());
if(x == 0) {
for(int j = a; j <= b; j++)
{
elems[j] = elems[j]^1;
}
segmentTree.constructSegmentTree();
}
else {
int num = segmentTree.getSum(a, b);
System.out.println(num);
}
}
}
}
編集：
GeeksForGeeks によると、ツリーの構築コストは O(n) で、更新方法は O(log n) です。したがって、更新のための新しいメソッドは次のとおりです。
private void updateTreeUtil(int startIndex, int endIndex, int updatePos, int update, int current)
{
if ( updatePos < startIndex || updatePos > endIndex)
{
return;
}
tree[current] = tree[current] + update;
if (startIndex != endIndex)
{
int mid = mid(startIndex, endIndex);
updateTreeUtil(startIndex, mid, updatePos, update, leftchild(current));
updateTreeUtil(mid+1, endIndex, updatePos, update, rightchild(current));
}
}
public void update(int update, int updatePos)
{
int updatediff = update - elems[updatePos];
elems[updatePos] = update;
updateTreeUtil(STARTINDEX, ENDINDEX, updatePos, updatediff, ROOT);
}
そして、main メソッドの if ループが次のように変更されました。
if(x == 0) {
for(int j = a; j <= b; j++)
{
segmentTree.update(elems[j]^1, j);
}
}
しかし、それでも TLE エラーが発生します。