结构体
struct SegentTreeNode { long long int value,lazytag; }; SegentTreeNode SegentTree[400010];
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
建树（一种lazytag）
void Build_tree(int root, int left, int right) { SegentTree[root].lazytag = 0;//默认是加减，所以取0，表示当前根节点下的节点都要+0（虽然加和没加值的大小都一样） if (left == right) { SegentTree[root].value = Data[left]; return;}//已经到了最底层了，可以赋值了 int mid = (left + right) >> 1; Build_tree(root << 1, left, mid ); Build_tree(root << 1 | 1, mid + 1, right); SegentTree[root].value = SegentTree[root << 1].value + SegentTree[root << 1 | 1].value; return; }
本质就是先往下一直找到最底层，然后递归赋值，一层一层往上面走
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
增减某区间的值
void Search_Tree(int root,int left, int right,int visleft,int visright,long long int add)//left和right是指当前root的左右范围，visleft和visright指要改动的区间 { if (right<visleft || left>visright) return; if (left >= visleft && visright >= right)//root的当前范围完全在要改区间内，也就是直接整体加减就足够了； { SegentTree[root].value += (long long int)(right-left+1)*add;//总共有几个，每个都要加add，所以一共加了这么多add； SegentTree[root].lazytag += add;//切记是+=，因为该root完全被覆盖，所以下面的暂时不用加，但是要记一下，之后如果调用的时候还是要加的 return; } int mid = left + right >> 1; Push_down(root,left,right);//传下lazytag，避免下面有的值漏加了，导致二叉树出错 Search_Tree(root << 1, left, mid, visleft, visright, add); Search_Tree(root << 1|1, mid+1, right, visleft, visright, add); SegentTree[root].value = SegentTree[root << 1].value + SegentTree[root << 1 | 1].value;//更新树的值 return; }
思路也还是一直先运算到最底层满足的，在从最底层往上递归更新值，就能实现改变底端值，上面的值也跟着改变的想法
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
乘除某区间数值（只有乘除）
void Mulity_Tree(int root, int left, int right, int visleft, int visright, long long int add2)//add2是要乘的值，mod是如果题目有要求取模才用，前面的值同上； { if (right<visleft || left>visright) return; if (left >= visleft && visright >= right) { SegentTree[root].value = SegentTree[root].value*add2 %mod;//下面的值*n，那么上面的值也是*n，而且只要乘一次，和加法有区别 SegentTree[root].lazytag2 = SegentTree[root].lazytag2 *add2%mod;//乘法须注意的点，往下乘的时候，加法的lazytag和乘法的lazytag值都要改变return; } int mid = (left + right) >> 1; Push_down(root, left, right); Mulity_Tree(root << 1, left, mid, visleft, visright, add2); Mulity_Tree(root << 1 | 1, mid + 1, right, visleft, visright, add2); SegentTree[root].value = (SegentTree[root << 1].value + SegentTree[root << 1 | 1].value) % mod; return; }
思路和加减类似，要额外注意两个lazytag都要改变；
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
加减混合乘除修改区间值
void Search_Tree(int root, int left, int right, int visleft, int visright, long long int add)//加减部分 { if (right<visleft || left>visright) return; if (left >= visleft && visright >= right) { SegentTree[root].value = (SegentTree[root].value+(long long int)(right - left + 1) * add)%mod; SegentTree[root].lazytag = (SegentTree[root].lazytag+ add)%mod; return; } int mid = (left + right )>> 1; Push_down(root, left, right); Search_Tree(root << 1, left, mid, visleft, visright, add); Search_Tree(root << 1 | 1, mid + 1, right, visleft, visright, add); SegentTree[root].value = (SegentTree[root << 1].value + SegentTree[root << 1 | 1].value)%mod; return; } void Mulity_Tree(int root, int left, int right, int visleft, int visright, long long int add2)//乘除部分 { if (right<visleft || left>visright) return; if (left >= visleft && visright >= right) { SegentTree[root].value = SegentTree[root].value*add2 %mod; SegentTree[root].lazytag2 = SegentTree[root].lazytag2 *add2%mod;//注意，在加减乘除混合的时候，乘除时要修改加减的lazytag和乘除的lazytag SegentTree[root].lazytag = SegentTree[root].lazytag * add2 % mod; return; } int mid = (left + right) >> 1; Push_down(root, left, right); Mulity_Tree(root << 1, left, mid, visleft, visright, add2); Mulity_Tree(root << 1 | 1, mid + 1, right, visleft, visright, add2); SegentTree[root].value = (SegentTree[root << 1].value + SegentTree[root << 1 | 1].value) % mod; return; }
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
lazytag使用
1）只有加减
void Push_down(int root,int left,int right) { if (!SegentTree[root].lazytag) return;//如果加减的lazytag是0的话，就说明这个根节点下的值都是真实值，不需要额外更新 long long int add = SegentTree[root].lazytag; int mid = (left + right) >> 1; SegentTree[root << 1].value += (long long int)(mid - left + 1) * add; SegentTree[root << 1|1].value += (long long int)(right - mid) * add;//改变左儿子和右儿子的值 SegentTree[root << 1 ].lazytag += add; SegentTree[root << 1|1].lazytag += add;//把lazytag传下去 SegentTree[root].lazytag = 0; return; }
2）加减混合乘除（先乘除后加减原则）
void Push_down(int root, int left, int right) { long long int add2 = SegentTree[root].lazytag2; long long int add = SegentTree[root].lazytag; int mid = (left + right) >> 1; SegentTree[root << 1].value = (SegentTree[root << 1].value*add2%mod+(long long int)(mid - left + 1) * add%mod)%mod; SegentTree[root << 1 | 1].value = (SegentTree[root << 1|1].value * add2%mod + (long long int)(right-mid) * add%mod ) % mod; SegentTree[root << 1].lazytag2 = SegentTree[root << 1].lazytag2*add2%mod;//先修改乘法的lazytag SegentTree[root << 1 | 1].lazytag2 = SegentTree[root << 1 | 1].lazytag2 * add2%mod; SegentTree[root << 1].lazytag = (SegentTree[root << 1].lazytag*add2+ add)%mod;//再修改加法的lazytag，修改加法的时候要记得有两步，既要乘也要加 SegentTree[root << 1 | 1].lazytag = (SegentTree[root << 1|1].lazytag * add2 + add) % mod; SegentTree[root].lazytag = 0; SegentTree[root].lazytag2 = 1; return; }
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
区间求和
long long int Find_sum(int root, int left, int right, int visleft, int visright) { if (right<visleft || left>visright) return 0;//不属于范围内的就+0 if (left >= visleft && right <= visright) return SegentTree[root].value; Push_down(root,left,right);//在读取或者修改的时候都要传lazytag，为了读取到真实的实时值 int mid = (left + right) >> 1; return Find_sum(root << 1, left, mid, visleft, visright)+ Find_sum(root << 1 | 1, mid + 1, right, visleft, visright);// }