我正在尝试解决这个 CodeChef 问题：
桌子上放着 N 个硬币，编号从 0 到 N - 1。最初，每个硬币都是反面朝上的。
您必须执行两种类型的操作：
翻转所有编号介于 A 和 B 之间的硬币。这由命令“0 A B”表示
回答在 A 和 B 之间编号的硬币有多少是正面的。这由命令“1 A B”表示。
输入：第一行包含两个整数，N 和 Q。接下来的 Q 行中的每一行都是上面提到的“0 A B”或“1 A B”的形式。
输出：为“1 A B”形式的每个查询输出 1 行，其中包含相应查询所需的答案。
我使用的是分段树。因此，每次用户输入类型 1 AB 的查询时，输出都是该区间 [A,B] 的总和。但是我收到了一个超出时间限制的错误。我相信错误是由于更新步骤 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 错误。