我使用标记法的线段树理论上应该更快啊，因为我先标记然后在向下查找迭代时处理子区间啊？而不使用标记法的每次都直接向下处理子区间还慢啊？但我在OJ上提交的结果反而是不使用标记法的更快，这是怎么回事啊？请大佬帮忙看看

不使用标记法的代码：

#define MAX_VAL 500000+5
#define MOD_NUM 80112002
#include <bits/stdc++.h>
using namespace std;
class Node{
    public:
        int left,right,val;
        vector<Pair> labels;
};
Node tree[4 * MAX_VAL];

int nums[MAX_VAL],ans,n,m;

void build(int left,int right,int ind){
    tree[ind].left = left,tree[ind].right = right;
    if(left==right) {tree[ind].val = nums[tree[ind].left];return;}
    int mid = left + (right - left)/2;
    build(left,mid,ind*2),build(mid+1,right,ind*2+1);
    tree[ind].val = tree[ind*2].val + tree[ind*2+1].val;
}

int get_sum(int left,int right,int ind){
    Node& node = tree[ind];
    if(node.left>=left&&node.right<=right){return node.val;}
    int ans = 0;
    if(tree[ind*2].right>=left) ans+=get_sum(left,right,ind*2);
    if(tree[ind*2+1].left<=right) ans+=get_sum(left,right,ind*2+1);
    return ans;
}

void add(int ind,int dist,int k){
    tree[ind].val += k;
    if(tree[ind].left==tree[ind].right) return;
    if(dist<=tree[ind*2].right) add(ind*2,dist,k);
    if(dist>=tree[2*ind+1].left) add(ind*2+1,dist,k);
}

bool redn(int& res){
    char ch=getchar();int cof = 1; res=0;
    if(ch==EOF) return false;
    while(ch>'9'||ch<'0') {if(ch=='-') cof = -1;ch=getchar();}
    while(ch>='0'&&ch<='9') res = res*10 + ch-'0',ch=getchar();;
    res *= cof;
    return true;
}
int main(int arg, char **argv)
{
    #ifdef LOCAL
        ifstream in(argv[1]);
        streambuf *cinbuf = cin.rdbuf(); //save old buf
        cin.rdbuf(in.rdbuf());           //redirect cin to file
        freopen("./input/input.in", "r", stdin);
    #endif
    redn(n),redn(m);
    for(int i=1;i<=n;i++) redn(nums[i]);
    build(1,n,1);
    for(int i=1;i<=m;i++){
        int op,x,k;
        redn(op),redn(x),redn(k);
        if(op==1) add(1,x,k);
        if(op==2){
            int ans = get_sum(x,k,1);
            cout<<ans<<endl;
        }
    }
    return 0;
}

使用标记法的：

#define MAX_VAL 500000+5
#include <bits/stdc++.h>
using namespace std;
class Pair{
    public:
        int ind,val;
    Pair(int ind,int val){this->ind=ind;this->val=val;}
};
class Node{
    public:
        int left,right,val;
        vector<Pair> labels;
};
Node tree[4 * MAX_VAL];

int nums[MAX_VAL],ans,n,m;

void build(int left,int right,int ind){
    tree[ind].left = left,tree[ind].right = right;
    if(left==right) {tree[ind].val = nums[tree[ind].left];return;}
    int mid = left + (right - left)/2;
    build(left,mid,ind*2),build(mid+1,right,ind*2+1);
    tree[ind].val = tree[ind*2].val + tree[ind*2+1].val;
}

// use labels
void add(int ind,int dist,int val){
    if(tree[ind].left>dist||tree[ind].right<dist) return;
    tree[ind].val += val;
    tree[ind].labels.push_back(Pair(dist,val));
} 

void pushdown(int ind){
    Node& node = tree[ind];
    for(int i=0;i<node.labels.size();i++){
        Pair& p = node.labels[i];
        int dist = p.ind,val=p.val;
        add(ind*2,dist,val),add(ind*2+1,dist,val);
    }
    node.labels.clear();
}

int get_sum(int left,int right,int ind){
    Node& node = tree[ind];
    pushdown(ind);
    if(node.left>=left&&node.right<=right){return node.val;}
    int ans = 0;
    if(tree[ind*2].right>=left) ans+=get_sum(left,right,ind*2);
    if(tree[ind*2+1].left<=right) ans+=get_sum(left,right,ind*2+1);
    return ans;
}

bool redn(int& res){
    char ch=getchar();int cof = 1; res=0;
    if(ch==EOF) return false;
    while(ch>'9'||ch<'0') {if(ch=='-') cof = -1;ch=getchar();}
    while(ch>='0'&&ch<='9') res = res*10 + ch-'0',ch=getchar();;
    res *= cof;
    return true;
}
int main(int arg, char **argv)
{
    redn(n),redn(m);
    for(int i=1;i<=n;i++) redn(nums[i]);
    build(1,n,1);
    for(int i=1;i<=m;i++){
        int op,x,k;
        redn(op),redn(x),redn(k);
        if(op==1) add(1,x,k);
        if(op==2){
            int ans = get_sum(x,k,1);
            cout<<ans<<endl;
        }
    }
    return 0;
}